%%
%% This is file `docultex.tex', 
%% Documentation for siam macros for use with LaTeX 2e
%% 
%% By Paul Duggan for the Society for Industrial and Applied
%% Mathematics. 
%% 
%% August 1, 1995
%%
%% Version 1.1a
%% 
%% You are not allowed to change this file. 
%% 
%% You are allowed to distribute this file under the condition that 
%% it is distributed together with all of the files in the siam macro 
%% distribution. These are:
%%
%%  siamltex.cls (main LaTeX macro for SIAM)
%%  siamltex.sty (includes siamltex.cls for compatibility mode)
%%  siam10.clo   (size option for 10pt papers)
%%  subeqn.clo   (allows equation numbners with lettered subelements)
%%  siam.bst     (bibliographic style file for BibTeX)
%%  docultex.tex (this file)
%%  lexample.tex (example file for latex macro)
%%
%% If you receive only some of these files from someone, complain! 
%% 
%% You are NOT ALLOWED to distribute this file alone. You are NOT 
%% ALLOWED to take money for the distribution or use of either this 
%% file or a changed version, except for a nominal charge for copying 
%% etc. 
%% \CharacterTable
%%  {Upper-case    \A\B\C\D\E\F\G\H\I\J\K\L\M\N\O\P\Q\R\S\T\U\V\W\X\Y\Z
%%   Lower-case    \a\b\c\d\e\f\g\h\i\j\k\l\m\n\o\p\q\r\s\t\u\v\w\x\y\z
%%   Digits        \0\1\2\3\4\5\6\7\8\9
%%   Exclamation   \!     Double quote  \"     Hash (number) \#
%%   Dollar        \$     Percent       \%     Ampersand     \&
%%   Acute accent  \'     Left paren    \(     Right paren   \)
%%   Asterisk      \*     Plus          \+     Comma         \,
%%   Minus         \-     Point         \.     Solidus       \/
%%   Colon         \:     Semicolon     \;     Less than     \<
%%   Equals        \=     Greater than  \>     Question mark \?
%%   Commercial at \@     Left bracket  \[     Backslash     \\
%%   Right bracket \]     Circumflex    \^     Underscore    \_
%%   Grave accent  \`     Left brace    \{     Vertical bar  \|
%%   Right brace   \}     Tilde         \~}


%\documentclass[final]{siamltex}
\documentclass{siamltex}

\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{times}
%\usepackage{fullpage}
\usepackage{amsfonts}
%\usepackage{algorithm}
\usepackage{mathrsfs}
\usepackage{eucal}
%\usepackage[lined,algonl,ruled]{algorithm2e}
\usepackage[ruled]{algorithm2e}
\usepackage{url}

%\setlength{\textheight}{9.4in} \setlength{\textwidth}{6.55in}
%\setlength{\textheight}{9.2in} \setlength{\textwidth}{6.55in}
%\setlength{\textheight}{9.15in} \setlength{\textwidth}{6.7in}
%\setlength{\topmargin}{0in}

%\voffset=-0.9in
%\hoffset=-0.7in


\newtheorem{thm}{\textbf{Theorem}}
\newtheorem{cor}[thm]{\textbf{Corollary}}
\newtheorem{lem}[thm]{\textbf{Lemma}}
%\newtheorem{lemma}[thm]{\textbf{Lemma}}
\newtheorem{prop}[thm]{\textbf{Proposition}}
%\theoremstyle{definition}
\newtheorem{defn}[thm]{\textbf{Definition}}
%\newtheorem{algorithm}[thm]{\textbf{Algorithm}}
\newcommand{\mbx}{\mathbf{x}}
\newcommand{\mbv}{\mathbf{v}}
\newcommand{\mby}{\mathbf{y}}
%\newcommand{\le}{\left}
%\newcommand{\ri}{\right}

%\ifx\pdfoutput\undefined
%\usepackage{graphicx}
%\else
%\usepackage[pdftex]{graphicx}
%\fi
%
%\usepackage{psfrag}
\usepackage{subfigure}
\usepackage{url}
\usepackage{appendix}
%define proof environment
\def\QED{\mbox{\rule[0pt]{1.5ex}{1.5ex}}}
\def\proof{\noindent\hspace{2em}{\itshape Proof: }}
\def\endproof{\hspace*{\fill}~\QED\par\endtrivlist\unskip}

%-------------------------------------------------------------------------
% take the % away on next line to produce the final camera-ready version

%-------------------------------------------------------------------------

%\renewcommand{\baselinestretch}{0.99}

%\date{}

%\begin{titlepage}
\title{Almost-Optimal Gossip-Based Aggregate Computation\thanks{A preliminary version of this paper was published in the proceedings of 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Greece, June, 2010, pages 124-133.}}
\author{
Jen-Yeu Chen\thanks{Department of Electrical Engineering, National DongHwa University, ShouFeng, Hualien 97401, Taiwan, ROC.
E-mail: {\tt jenyeuchen@acm.org}. Supported in part by NSC Grant NSC98-2221-E259-010.}
\and Gopal
Pandurangan\thanks{Division of Mathematical Sciences, Nanyang Technological 
University, Singapore 648477, and Department of Computer Science, Brown University, Providence, RI 02912, USA. E-mail:~{\tt gopalpandurangan@gmail.com}. Supported in part by NSF Award  CCF-1023166.}
}


\begin{document}
\maketitle

\begin{abstract}
Motivated by applications to modern networking technologies,  there has been   interest in designing  efficient gossip-based protocols for computing aggregate functions. While gossip-based protocols provide robustness due to their randomized nature, reducing the message and time complexity of these protocols is also of paramount importance in the context of resource-constrained networks such as sensor and peer-to-peer networks.

We present  provably time-optimal efficient gossip-based algorithms for aggregate computation with almost optimal message complexity. Given a $n$-node  network, our algorithms guarantee that all the nodes can compute the common aggregates (such as $Max$, $Min$, $Average$, $Sum$, $Count$, etc.)  of their values in optimal $O(\log n)$ time and using $O(n \log \log n)$ messages.
Our result improves on the  algorithm  of Kempe et al.~\cite{kempe} that is time-optimal, but uses $O(n \log n)$ messages as well as on the algorithm of Kashyap et al.~\cite{efficient-gossip} that uses $O(n \log \log n)$ messages, but is not time-optimal (takes $O(\log n \log \log n)$ time). Furthermore, we  show that our algorithms can be used to
improve gossip-based aggregate computation in  sparse communication networks, such as in peer-to-peer networks. 

The main technical ingredient of our algorithm is a  technique called {\em distributed random ranking (DRR)} that can be useful in other applications as well.  DRR  gives an efficient distributed procedure to  partition the network into a forest of  (disjoint) trees of small size. Since the  size of each tree is small,  aggregates within each  tree can be efficiently obtained at their respective roots.
All the roots then perform a uniform gossip algorithm on their local aggregates to reach a distributed consensus on the global aggregates.

Our algorithms are non-address-oblivious. In contrast, we show a lower bound of $\Omega(n\log n)$ on the message complexity of any address-oblivious algorithm for computing aggregates. This shows that  non-address-oblivious algorithms  are needed to obtain significantly better message complexity. Our lower bound holds regardless of the number of rounds taken or the size of the messages used.   Our lower bound is the first non-trivial lower bound for gossip-based aggregate computation and  also gives the first formal proof that  computing aggregates is strictly harder than
 rumor spreading in the address-oblivious model. 
\end{abstract}


\begin{keywords} 
Gossip-based protocols, aggregate computation, distributed  randomized protocols, probabilistic analysis, lower bounds
\end{keywords}

\begin{AMS}
68M14, 68M11, 68M12,  68Q25, 68W40, 68W15, 68W20,  68P20
\end{AMS}

\pagestyle{myheadings}
\thispagestyle{plain}
\markboth{J.-Y. Chen AND G. Pandurangan}{Almost-Optimal Gossip-Based Aggregate Computation}

%\end{titlepage}

%\vspace*{-0.1in}
\section{Introduction}
%\vspace*{-0.12in}
\subsection{Background and Previous Work}
%\vspace*{-0.05in}

Aggregate statistics (e.g., $Average$, $Count$, $Max$, $Min$, and $Sum$ etc.)  are significantly useful for many applications in networks~\cite{DRG-SHS,DRG,sparse-aggregation,Jelasity-tocs,kempe,impact-aggregate,aggregation-service,sensys04-1}. These statistics
have to be computed over data stored at individual nodes. For example, in a peer-to-peer network, the average number of files stored at each node or the maximum size of files exchanged between nodes is  an important statistic needed by system designers for optimizing overall performance~\cite{pastry,chord}. Similarly, in sensor networks,  knowing the average or maximum remaining battery power among the sensor nodes is a critical statistic.
Many research efforts have been dedicated to developing scalable and distributed algorithms  for aggregate computation.  Among them
gossip-based algorithms~\cite{S-Boyd-gossip,DRG,geographic-gossip,efficient-gossip,kempe,smart-gossip,separable-gossip,sensys04-2,Gossip-Roberto-podc08,hierarchical-gossip} have recently received significant attention because of their simplicity of  implementation, scalability to large network size, and robustness to frequent network topology changes.
 In a gossip-based algorithm,  each node  exchanges  information with a randomly chosen communication partner in each round.  The randomness inherent in the gossip-based protocols naturally provides robustness, simplicity, and scalability~\cite{Karp-rumor,efficient-gossip}. We refer to~\cite{Karp-rumor,efficient-gossip,kempe} for a detailed discussion on the   advantages of  gossip-based computation over centralized
 and deterministic approaches and their attractiveness to emerging networking technologies such as peer-to-peer, wireless, and sensor networks. This paper focuses on designing efficient gossip-based protocols for aggregate computation that
 have low message and time complexity. This is especially useful in the context of resource-constrained networks
 such as sensor and  wireless  networks, where reducing message and time complexity can yield significant benefits
 in terms of lowering congestion and lengthening node lifetimes.

\iffalse
%%%%%%%%%%%% the following two paragraphes are added by JY 11/27/2010
The problem of aggregate computation by (epidemic) gossip-based algorithms is different from the two fundamental information dissemination problems, namely, broadcasting\footnote{The broadcasting problem here is also different from the broadcasting transmission, or the broadcast, in wireless communications where a broadcasting transmission is to transmit a message (information) to all the other nodes in the wireless radio coverage by the broadcasting nature of a wireless radio media.} and gossiping\footnote{A gossiping problem is different from a gossip algorithm. A gossiping problem is not necessarily solved by a  gossip-based algorithm; it can be tackled by some deterministic algorithms as well.}. In broadcasting, the goal is to spread an information (message) throughout the network, i.e., a one-to-all information dissemination whereas in gossiping every node distributes their information (messages) to all the other nodes in the network, i,e, an all-to-all total information exchange. Intuitively, the gossiping problem is at least as hard as the broadcasting problem if all the nodes disseminate their information out simultaneously in the beginning of the gossiping problem.
%unless two or more messages in gossiping counter each other so that a node received two contradicting messages will not send out both of them. 

In general, the aggregate computation problem and the gossiping problem are as hard in complexity when they are solved by gossip-based algorithms. The aggregates could be easily obtained by off-line computation after solving the corresponding gossiping problem since eventually every node, in the gossiping problem, can acquire all the nodes' information (values). However, for every node to know the individual information of the other nodes, the local information processing procedure such as aggregation or fusion at each node is not allowed in the algorithms solving the gossiping problem, meaning that in the late stage of these algorithms, the size of an outgoing message could be very large, e.g., in $O(n)$. On the other hand, in aggregate computation problem, what really matter is the the aggregate statistics but not the individual information (value) of each node. Thus, for the algorithms designed for aggregate computation such as ours in this paper, each node can perform  aggregation or fusion to keep the size of the outgoing messages in a certain $O(1)$ length. Nevertheless, to obtain the correct aggregate (or say, the accurate estimate of the aggregate) at each node, in the end, every node's information needs to be well disseminated over the network, the same final result of the gossiping problem. Thus, by applying gossip-based algorithms, the problem of computing aggregates is as hard as the gossiping problem.                 

%%%%%%%%%%%%%%%%%
\fi
Much of the early work on the gossip algorithm focused on using randomized communication for rumor propagation (a {\em broadcasting} problem)~\cite{demers,Karp-rumor,pittel}. In particular, Karp et al. \cite{Karp-rumor} gave a rumor spreading algorithm (for spreading a single message throughout a network of $n$ nodes)  that takes $O(\log n)$ communication rounds and $O(n \log \log n)$ messages.
It is easy to establish that $\Omega(\log n)$ rounds are needed by any gossip-based rumor spreading algorithm
(this bound also holds for gossip-based aggregate computation).
They also showed that any rumor spreading algorithm needs  at least $\Omega(n \log \log n)$ messages for a class of randomized gossip-based algorithms referred to as {\em address-oblivious} algorithms \cite{Karp-rumor}.    Informally, an algorithm is called address-oblivious  if  the decision to send a message to its communication partner in a round does not depend on  the partner's address. Karp et al.'s algorithm is address-oblivious. For non-address oblivious algorithms, they show a lower bound of $\omega(n)$ messages,
if the algorithm is allowed only $O(\log n)$ rounds.

  Kempe et al.~\cite{kempe} were the first to present randomized gossip-based algorithms for computing aggregates. They analyzed a  gossip-based protocol for computing sums, averages, quantiles, and other
aggregate functions. In their scheme for estimating  average, each node selects another random node to which it sends half of its value; a node on receiving a set of values just adds them to its own halved value. Their protocol  takes $O(\log n)$  rounds and uses $O(n \log n)$ messages to converge to the true average in a $n$-node  network. Their protocol is address-oblivious.  The work of Kashyap et al.~\cite{efficient-gossip} was  the first to address the issue of reducing the message complexity of gossip-based aggregate protocols, even at the cost of increasing the time complexity.  They presented an algorithm that significantly improves over the message
complexity of the protocol of Kempe et al. Their algorithm uses only $O(n \log \log n)$ messages, but is not time optimal --- it runs in $O(\log n \log \log n)$ time. Their algorithm achieves this $O(\log n/\log \log n)$ factor reduction
in the number of messages by randomly clustering nodes into groups of size $O(\log n)$, selecting representative for each group, and then having the group representatives gossip among themselves. Their algorithm is not  address-oblivious.
For other related work on gossip-based protocols, we refer to~\cite{DRG,efficient-gossip} and the references therein.
%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{table*}
% increase table row spacing, adjust to taste
%\renewcommand{\arraystretch}{1.3}
\caption{DRR-gossip vs. other gossip-based algorithms.}\label{table-performance-DRR-gossip}
\begin{center}
% Some packages, such as MDW tools, offer better commands for making tables
% than the plain LaTeX2e tabular which is used here.
\begin{tabular}{lccc}
  \hline \hline
  Algorithm & time complexity & message complexity & address oblivious\\
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
   %\hline
  efficient gossip~\cite{efficient-gossip} & $O(\log n \log\log n )$ & $O(n\log\log n)$ & no\\ 
  %\hline
  uniform gossip~\cite{kempe}& $O(\log n)$ &$O(n\log n)$ & yes\\
 DRR-gossip~[this paper] & $O(\log n)$ & $O(n\log\log n)$ & no \\

  \hline \hline
 % \multicolumn{3}{l}{The gossip-based algorithms in~\cite{S-Boyd-gossip,geographic-gossip} are based on a different assumption of network model.}\\
 \end{tabular}
\end{center}
\end{table*}
%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\vspace*{-0.1in}
\subsection{Our Contributions}
%\vspace*{-0.05in}
%
%
%
%
%\begin{table*}
%% increase table row spacing, adjust to taste
%%\renewcommand{\arraystretch}{1.3}
%\caption{DRR-gossip vs. other gossip-based algorithms.}\label{table-performance-DRR-gossip}
%\begin{center}
%% Some packages, such as MDW tools, offer better commands for making tables
%% than the plain LaTeX2e tabular which is used here.
%\begin{tabular}{lccc}
%  \hline \hline
%  Algorithm & time complexity & message complexity & address oblivious? \\
%  \hline
%  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%   %\hline
%  efficient gossip~\cite{efficient-gossip} & $O(\log n \log\log n )$ & $O(n\log\log n)$ & no\\ 
%  %\hline
%  uniform gossip~\cite{kempe}& $O(\log n)$ &$O(n\log n)$ & yes\\
% DRR-gossip~[this paper] & $O(\log n)$ & $O(n\log\log n)$ & no \\
%
%  \hline \hline
% % \multicolumn{3}{l}{The gossip-based algorithms in~\cite{S-Boyd-gossip,geographic-gossip} are based on a different assumption of network model.}\\
% \end{tabular}
%\end{center}
%\end{table*}
%%
%
%
%
%
%In this paper,  

We present  improved gossip-based algorithms  for  computing various  aggregate functions. Given a $n$-node  network, our algorithms guarantee that all the nodes can compute the common aggregates (such as $Min$/$Max$,  $Average$, $Sum$, $Count$ etc.)  of their values in
optimal $O(\log n)$ time and using $O(n \log \log n)$ messages.
Our result  (cf. Table~\ref{table-performance-DRR-gossip}) improves on the  algorithm  of Kempe et al.~\cite{kempe} (called as ``uniform gossip")   that is time-optimal, but uses $O(n \log n)$ messages as well as on the algorithm of Kashyap et al. \cite{efficient-gossip}  (called as "efficient gossip") that uses $O(n \log \log n)$ messages,
but is not time-optimal (takes $O(\log n \log \log n)$ time).
%Please see Table~\ref{table-performance-DRR-gossip} for the complexity comparison amid these three gossip-based algorithms. Also, we note that the gossip-based algorithms in~\cite{S-Boyd-gossip,geographic-gossip} are under a different network model assumption. Although DRR-gossip outperform them in both time and message complexities, a direct comparison of their performance with DRR-gossip's  is unfair.
%We note that the gossip-based algorithms of~\cite{S-Boyd-gossip,geographic-gossip} are under a different network model compared to the one used in this paper and those of Kempe et al. and Kashyap et al.
%Although our  algorithm, DRR-gossip,  outperforms them in both time and message complexities, it is unfair to directly compare their performance (derived on a different network model)
%with our algorithm's.

Our algorithms use a simple  scheme called {\em distributed random ranking (DRR)}  that gives an efficient distributed protocol to partition the network into a forest of  disjoint trees of $O(\log n)$ size. Since the size of each tree is small,  aggregates within each  tree can be efficiently obtained at their respective roots.
All the roots then perform a uniform gossip algorithm on their local (tree) aggregates to reach a distributed consensus on the global aggregates.  Our  idea of forming trees and then doing gossip among the roots of the trees  is similar to the idea  of Kashyap et al.  The main novelty  is that our DRR technique gives a simple and efficient  distributed way of decomposing the network into disjoint trees (groups) which takes
only $O(\log n)$ rounds and $O(n \log \log n)$ messages.  This leads to a simpler and faster algorithm than that
of \cite{efficient-gossip}.  The paper  of \cite{Gossip-Roberto-podc08}  proposes the following heuristic: divide the network into clusters  (called the ``bootstrap phase"), aggregate the data within the clusters --- these are aggregated
in a small subset of nodes  within each cluster called clusterheads; the clusterheads then use gossip algorithm of Kempe et al  to do inter-cluster aggregation; and, finally the clusterheads will disseminate the information to all the nodes in the respective clusters.  It is not clear in~\cite{Gossip-Roberto-podc08} how to efficiently implement  the bootstrap phase of dividing the network into clusters. Also, only numerical simulation results are presented in~\cite{Gossip-Roberto-podc08} to show that their approach gives better complexity than the algorithm of Kempe et al.
%Also, in \cite{Gossip-Roberto-podc08} numerical simulation results are presented to show that their approach gives better complexity than the algorithm of Kempe et al.
It is mentioned {\em without proof} that their approach can take $O(n \log \log n)$ messages and $O(\log n)$ time.
Hence, to the best of our knowledge, our work presents the first rigorous protocol that provably shows these bounds.

Our second contribution is analyzing gossip-based aggregate computation
in sparse  networks.
In  sparse topologies  such as P2P networks, point-to-point communication  between all pairs of nodes (as assumed in gossip-based protocols)
may not be a reasonable assumption. On the other hand, a small
number of neighbors  in such networks makes it feasible to send one message simultaneously to
all  neighbors in one round: in fact, this is a standard assumption in the distributed message passing model \cite{peleg}.  We show how our DRR technique leads to
improved  gossip-based aggregate computation in such (arbitrary) sparse networks, e.g.,
 P2P network topologies such as Chord \cite{chord}.  The improvement
relies on a key property of the DRR scheme that we prove:  {\em height} of each tree produced by DRR in any {\em arbitrary} graph is
   bounded by $O(\log n)$ whp\footnote{Throughout the paper, ``with high probability (whp)" means ``with probability at least $1 - 1/n^{\alpha}$, for some constant $\alpha > 0$".
}.  In Chord, for example, we show that DRR-gossip takes $O(\log^2 n)$ time whp and $O(n\log n)$ messages. In contrast,  uniform gossip gives $O(\log^2 n)$ rounds and $O(n \log^2 n)$ messages.


Our algorithm is non-address oblivious, i.e., some steps use addresses to decide which partner to communicate in a round. In particular, our algorithm  is mostly  address-oblivious, except for one step (the address forwarding step in Phase 2).  This does reduces the robustness  a bit but it helps improve over the  complexity of the standard gossip. The time complexity of our algorithm is optimal. The message complexity is  within
a factor $o(\log \log n)$ of the optimal because Karp et al \cite{Karp-rumor} showed a lower bound of $\omega(n)$ for any non-address oblivious
rumor spreading algorithm that operates in $O(\log n)$ rounds.  (Computing aggregates is at least as hard as rumor spreading --- see Section 2 for an argument.)



 Our third contribution is a non-trivial lower bound of $\Omega(n\log n)$ on the message complexity of any address-oblivious algorithm for computing aggregates. This lower bound holds regardless of the number of rounds taken or the size of the messages (i.e., even assuming that nodes that can send arbitrarily long messages).   Our result shows that non-address oblivious algorithms (such as ours) are needed to obtain a significant improvement in message complexity.
 We note that this bound is significantly larger than the $\Omega(n \log \log n)$ messages shown by Karp et al. for rumor spreading. Thus our result  also gives the first formal proof that  computing aggregates is strictly harder than
 rumor spreading in the address-oblivious model. Another implication of our result  is that the algorithm of Kempe et al.~\cite{kempe} is asymptotically message optimal for the address-oblivious model.


\subsection{Related Work and Comparison}
The recent work of Berenbrink et al. \cite{Berenbrink-icalp10} studies the general gossiping problem in the random phone call model of Karp et al.\cite{Karp-rumor}. In the gossiping problem, the task of each node is to send its message to every other node, i.e.,
the requirement is {\em total information exchange} between all nodes. Note that, this is somewhat a stronger requirement than computing aggregates. Clearly,
an algorithm that does gossiping can be easily used to compute aggregates or any other function of the values at  the $n$ nodes.  
However, a standard assumption
in gossiping is that messages  received by a node (and its initial message) can be combined together (without message-shorten processing such as fusion or aggregation) and subsequently transmitted as a single message; hence message sizes can be quite large, say up to $O(n)$ bits. In contrast, in aggregate computation, typically  only small (logarithmic) size messages is allowed (as used in this paper and in previous literature~\cite{efficient-gossip,kempe}).  Thus  algorithms for the gossiping problem do not directly lead  to efficient aggregate computation.  Also, in this context, we mention the work in~\cite{G2-Alistarh-icalp10,G1-Gilbert-soda10}  that manages to obtain {\em fault-tolerant} gossip algorithms with $O(n)$ message complexity and logarithmic time complexity  by allowing nodes to send more than one message per round, e.g., a node can send $O(n)$ messages in a round. However, in this paper 
as well as in previous literature on random phone call model~\cite{Karp-rumor,efficient-gossip,kempe}, we allow a node to send only one message (or a constant number of messages) per round.


In the above model, Berenbrink et al.  present a lower bound of $\Omega(n \log n)$message complexity for any $O(\log n)$-time randomized gossiping algorithm, with probability $1-o(1)$.  This can be seen as a separation result between broadcasting (i.e., rumor spreading) and gossiping in the random phone-call model. Our lower bound (i.e., $\Omega(n \log n)$) also applies to the gossiping problem (total information exchange), since our lower bound proof
also implies the same  lower bound for the gossiping problem in the random phone call model. (Our proof bounds the message complexity of sending $n^{\Omega(1)}$ messages to $\Omega(n)$ nodes.) However there are difference between the two lower bounds (i.e., ours verses Berenbrink et al.).
 First, our model is somewhat less general than the definition of ``address-oblivious"  as given in \cite{Karp-rumor} (which is also the model used in Berenbrink et al.),
where a node's decision to communicate with its partner (chosen randomly) can depend on the addresses of the partners chosen in the previous communication rounds.  In our case, the decision whether a node sends a message to its communication partner (which is chosen randomly) does not depend on the partner's address nor on the knowledge of the {\em addresses} of the  partners seen in previous rounds. However, the decision to communicate may depend
on the value(s) acquired by the node  till now or other factors (e.g., a node may choose not to communicate for a long period of time). 
Second, our  result can be considered stronger in the sense that it does not assume any bound on the running time of the algorithm (although the nodes have less information about the system when making random choices). 






\subsection{Probabilistic Preliminaries}
\label{sec:prelim}

 We  use Doob martingales  extensively in our analysis \cite{random-alg-book}. Let $X_0, \dots, X_n$ be {\em any} sequence of random variables
and let $Y$ be any random variable with $E[|Y|] < \infty$.
Define the random variable $Z_i = E[Y|X_0, \dots, X_i]$, $ i =
0,1,\dots,n$.
Then $Z_0, Z_1, \dots, Z_n$ form a {\bf Doob martingale} sequence.

We use the martingale inequality  known as Azuma's inequality, stated as follows \cite{random-alg-book}.
Let $X_0, X_1, \dots $ be a martingale sequence such that for each
$k$,
\[ |X_k - X_{k-1}| \leq c_k\] where $c_k$ may depend on $k$.
Then  for all $t \geq 0$ and any $\lambda > 0$,
\begin{equation}
\label{eq:azuma} \Pr(|X_t - X_0| \geq \lambda ) \leq 2 e^{-
\frac{\lambda^2}{2\sum_{k=1}^tc_k^2}}
\end{equation}

We also use the following variant of the
Chernoff bound from~\cite{Srinivasan}, that works in the case of
dependent  indicator random variables that are  correlated as
defined below.

\begin{lemma}(\cite{Srinivasan})
\label{lem_fkg} Let $Z_1,Z_2,\ldots,Z_s \in \{0,1\}$ be random
variables such that for all $l$, and for any $S_{l-1} \subseteq
\{1,\ldots,l-1\}, \Pr(Z_l = 1 | \bigwedge_{j \in S_{l-1}} Z_j=1)
\leq \Pr(Z_l = 1)$. Then for any $\delta > 0$,
$\Pr(\sum\limits_{l=1}^{s}Z_l \geq \mu(1+\delta)) \leq
(\frac{e^{\delta}}{(1+\delta)^{1+\delta}})^{\mu}$, where $\mu =
\sum\limits_{l=1}^{s}E[Z_l]$.
\end{lemma}

\subsection{Paper Organization}
The rest of this paper is organized as follows. The network model is described in Section~\ref{sec:network model} followed by sections where each phase of the DRR-gossip algorithm is introduced and analyzed separately. The whole DRR-gossip algorithms to compute $Average$ and $Max$ are summarized in Section~\ref{sec:whole algorithm}. Computing other aggregates is described in Section~\ref{sec:other-aggregate}. Section~\ref{sec:p2p} applies DRR-gossip to sparse networks. An lower bound on the message complexity of any address-oblivious algorithm for computing aggregates is presented and proved in Section~\ref{sec:lbound-add-oblivious}. We conclude in Section \ref{sec:conclusion}.

%Due to space limitation, some pseudo-codes and proofs are not shown in this paper.  Interested readers are referred to the full version of this paper~\cite{full-version} for details.
%For convenience, Appendix~\ref{sec:prelim} lists the main probabilistic tools   used in our analysis.

%Simulation results are provided in Section~\ref{sec:simulation}.
%In Section~\ref{sec:lbound-add-oblivious}, we establish a   lower bound for the address oblivious model. We conclude in Section \ref{sec:conclusion}.

%\vspace*{-0.15in}
\section{Model}\label{sec:network model}
%\vspace*{-0.05in}
The network $G(V)$ consists of a set $V$ of $n$ nodes; each node $i \in V$ has a data value denoted by $v_i$. All  the node values form a value vector $\mathbf{v}=[v_i]$. The goal is to compute aggregate functions such as $Min$, $Max$, $Sum$, $Average$ etc., over $\mathbf{v}$ in a distributed manner. We next describe the model used in our paper.

The nodes communicate in  discrete time-steps referred to as {\em rounds}. As in prior work on this problem \cite{Karp-rumor, efficient-gossip}, we assume that rounds are synchronized and all nodes can communicate simultaneously in a given round.   Each node can communicate with every other node. In a round, each node can choose a communication partner independently and uniformly at random. 
As in previous work~\cite{Karp-rumor, kempe}, choosing a random partner is taken as a primitive, i.e., no assumptions are made on how this is implemented. Note that the above previous work assumes a point-to-point
communication model between all pairs of nodes, i.e., the underlying graph model 
is complete. (Presumably it is easy to select a random partner in a complete
graph model, since a node has to simply sample a random edge out of itself.)  Our algorithm detailed in Section 3  assumes the same model.
In Section 4, we consider a more realistic communication model where the
underlying graph can be an arbitrary (in particular, sparse) graph.  We refer to
Section 4 for  details.

 A node $i$ is said to {\em call} a node $j$ if $i$ chooses $j$ as a communication partner.  Once a call is established, we assume that information can be exchanged in both directions along the link. Two types of messages can be identified based on the direction of the message: A {\em push} message is one that is sent by a calling node to the called node and a {\em pull} message is the message obtained by the calling node from the called node.  In one round, a node can call only {\em one}  other node.    We assume that nodes have unique addresses.  Furthermore,  we  assume that  nodes initially have only local knowledge, i.e., they  start off with knowing only
their own address and data value. They do not have any information about  other nodes' addresses or data values. (However, we assume that they know $n$ the total number of players.)   The length of a message is limited to $O(\log n + \log s)$, where $s$ is the range of values.
 It is important to limit the size of messages  used in aggregate computation, as communication bandwidth is often a costly resource in distributed settings.  All the above assumptions
are also used in prior work~\cite{efficient-gossip,kempe}.

The above model is similar (but not the same) as the {\em random phone call} model as defined in Karp et al. \cite{Karp-rumor}). This model was first used in the Karp et al. paper to study rumor spreading via gossip and has subsequently been used
(possibly with some changes) to study other computation problems via gossip
such as aggregation.
The differences  are partly 
 due to the fact that we are dealing with different problems: rumor spreading
versus aggregate computation. (Note that  rumor spreading can be thought of as  a special case of aggregate computation --- we can adapt an algorithm for computing the  Max to do rumor spreading, e.g., by appending the rumor node with a large value. Hence, rumor spreading is not harder than computing aggregates.)  One difference is that, in  Karp et al., it is assumed that there is a special node that starts with a rumor (which is implicit in their model), whereas in our model,
there is no such special (or leader) node.   
However, the main difference is that while the  algorithm of Karp et al. follows an {\em address-oblivious} random phone call, ours does not.
 In an address-oblivious random phone call model,    a node's decision to communicate  in a round  does not depend on its currently chosen partner's address (the partner itself is chosen randomly in each round.)
 In contrast, in our model, while most of the rounds involve choosing partner in a random fashion and communicating in an address-oblivious fashion,
some steps are not. In these steps, a node chooses a partner not  randomly, but  based on its address (which it gets to know during the course of the algorithm).  In our algorithm such a step only arises
in Phase 3 (cf. Section \ref{sec:phase3}). 


 % Our algorithm can tolerate the following types of failures (similar to the algorithms of  \cite{efficient-gossip,kempe}). In particular, we assume two types of failures: (i) some fraction of nodes may crash initially, and (ii) links are lossy and messages can get lost.
Similar to the algorithms of  \cite{efficient-gossip,kempe}, our algorithm can tolerate the following two types of failures: (i) some fraction of nodes may crash initially, and (ii) links are lossy and messages can get lost.
Thus, while nodes cannot fail once the algorithm has started, communication can fail with a certain probability
$\delta$.
Without loss of generality,  $1/\log n < \delta < 1/8$ (or some such small constant):  Larger values of $\delta$, requires only $O(1/\log(1/\delta))$ repeated calls to bring down the probability below $1/8$,  and smaller values only make it easier to prove our claims.



%Without loss of generality, $1/\log n < \delta < 1/8$. It requires only $O(1/\log(1/\delta))$ repeated calls to bring down the larger values of $\delta$ below $1/8$.  Smaller values of $\delta$ only make it easier to prove our claims.

%Throughout the paper, ``with high probability (whp)" means ``with probability at least $1 - 1/n^{\alpha}$, for some constant $\alpha > 0$".

%--------------------------algorithm DRR----
\begin{algorithm}[t]
\label{alg:DRR}
%\dontprintsemicolon % for Miktex previous versions
\dontprintsemicolon  % for Miktex 2.8
  \caption{$\mathbb{F}=$DRR($G$)}
%  \begin{algorithmic}[1]
  \ForEach{node $i\in V$}
  {
 %choose $p(i)$ uniformly at random from $[0,1]$ \;
  choose $rank(i)$ independently and uniformly at random from $[0,1]$ \;
  set {\it found $=$ FALSE}   // higher ranked node not yet found \;
  set $parent(i)$$=${\it NULL} // initially every node is a root node\;
  set $k = 0$   // number of random nodes probed \;
  \Repeat{found $==$ TRUE or $k > \log n - 1$}
  {sample  a node  $u$  independently and uniformly at random from $V$ and get its rank \;
   \If{$rank(u)  >  rank(i)$}
   {set $parent(i) = u$\; set {\it found $=$ TRUE}\;
   set $k = k+ 1$\;}
   }
  % \Until{$found ==TRUE$ or $k < \log n - 1$}

   \If{found $==$ TRUE}
    %{set $parent(i)=\text{NULL}$, and become a root node.}
   {send a connection message including its identifier, $i$, to its parent node $parent(i)$\;}
   Collect the connection messages and accordingly construct the set of its children nodes, $Child(i)$\; %on its associated tree
   \eIf{$Child(i)=\emptyset$}
   {become a leaf node\;}
   {become an intermediate node\;}
   } %foreach
\end{algorithm}

%\vspace*{-0.1in}
\section{DRR-Gossip Algorithms}
Our  algorithm, henceforth called {\em DRR-gossip},  proceeds in phases. In phase one, every  node runs the DRR scheme to construct a forest of (disjoint) trees.
In phase two, each tree computes its  local aggregate (e.g., sum or maximum)  by a convergecast process; the  local aggregate is obtained at the root.
Finally in phase three, all the roots  utilize a suitably modified version of the uniform gossip algorithm of Kempe et al.~\cite{kempe} to obtain the global aggregate. Finally, if necessary, the roots forward the global aggregate  to other nodes in their trees.
We describe the detail of each phase in the following sections. We start with the description of the algorithm of Distributed Random Ranking (DRR).%\vspace*{-0.1in}
%\subsection{Phase I: Distributed Random Ranking (DRR)}
\subsection{Phase I: Distributed Random Ranking}
%\vspace*{-0.1in}
%%\subsubsection{The DRR algorithm}
The Distributed Random Ranking (DRR) algorithm is as follows (cf. Algorithm~\ref{alg:DRR}).
% in Appendix~\ref{apx:DRR}).
Every node $i\in V$ chooses  a rank independently and uniformly
at random from $[0,1]$. (Equivalently, each node can  choose a  rank  uniformly at random from $[1,n^3]$ which leads to the same asymptotic bounds; however, choosing from $[0,1]$ leads to a smoother analysis, e.g., allows use of integrals.)  Each node $i$  then
samples up to $\log n -1$   random nodes sequentially (one in each round) till it finds a node of higher rank to connect to.  If none of the $\log n -1$ sampled  nodes have a higher rank then node $i$ becomes a ``root".  Since every node except root nodes connects to a node with higher rank, there is no cycle in the graph.   Thus this process results in a collection of disjoint trees which together constitute a forest $\mathbb{F}$.  

In the following two theorems, we show the upper bounds of the number of trees and  the size of each tree produced by the DRR algorithm; these are critical in bounding the time complexity of DRR-gossip.

%\subsection{Number of Trees}
%\vspace*{-0.1in}
\begin{thm}[Number of Trees]
\label{le:numtrees}
The number of  trees produced by the DRR algorithm is $O(n/\log n)$ whp.
\end{thm}
%-------------------

%\vspace*{-0.1in}
\proof
%The probability that a node $i$ becomes a root is $\Theta(1/\log n)$, because this is the probability that
%its rank is highest among all the $\log n - 1$ nodes probed.
%
%
%To  show tight concentration, we use the following argument.
Assume that ranks have already been assigned to the nodes.  All ranks are distinct with probability~1.   Number the nodes according to the order statistic of their ranks: the $i$th node is the node with
the $i$th smallest rank. Let the indicator random variable $X_i$  take the value of 1 if the $i$th smallest node is
a root and 0 otherwise.  %(Note that probability that $X_n = 1$ is 1 and the probability that $X_0 = 1$ is 0.)
Let $X = \sum_{i=1}^n X_i$ be the total number of roots.  %As shown above, $E[X] = O(n/\log n)$.
The $i$th smallest node becomes a root if all the nodes that it samples have rank smaller than or equal to itself, i.e.,
 $ \Pr(X_i = 1) =  \left( \frac{i}{n}\right)^{\log n - 1}.$
 Hence, by linearity of expectation, the expected number of roots (and thus, trees) is:
 \begin{align*}
 E[X] &= \sum_{i=1}^n \Pr \left(X_i = 1\right) = \sum_{i=1}^n \left( \frac{i}{n}\right)^{\log n - 1}\\ 
      &= \Theta \left( \int_1^n \left(\frac{i}{n}\right)^{\log n - 1}\,d\,i \right) =   \Theta \left( \frac{n}{\log n} \right).
 \end{align*}
Note that $X_i$s are independent (but  not identically distributed) random variables, since the probability that the $i$th smallest ranked
node becomes the root depends only on the $\log n-1$  random nodes that it samples and independent of the samples of the rest of the  nodes.  Thus, applying a Chernoff bound~\cite{random-alg-book}, we have
$\Pr(X > 6 E[X]) \leq 2^{E[X]} = o(1/n).$
\endproof

%The next lemma bounds the size of any tree formed in phase I.

%\vspace*{-0.1in}
%\subsection{Tree Size}
%\vspace*{-0.05in}

%We can show that the height of every tree produced by the DRR algorithm to be $O(\log n)$ whp (proof in Appendix). We will show something even stronger. We will show that the number of nodes in every tree  is at most $O(\log n)$ whp (thus height is also bounded by $O(\log n)$ whp).
%\vspace*{-0.1in}
\begin{thm}[Size of a tree]
\label{le:sizeoftree}
The number of nodes in every tree produced by the DRR algorithm is at most $O(\log n)$ whp.
\end{thm}

%\vspace*{-0.1in}
\proof
We show that the probability that a tree of size $\Omega(\log n)$ is produced by the DRR algorithm goes to zero asymptotically.
Fix a set $S$ of $k = c \log n$ nodes, for some sufficiently large positive constant $c$.
We first compute the probability that a (spanning) tree of size $k$ is constructed over this set of $k$ nodes by the DRR algorithm.
For the sake of analysis, we direct tree edges as follows: a tree edge $(i,j)$ is directed  from  node $i$ to node $j$ if  $rank(i) < rank(j)$, i.e. $i$ connects to $j$. Without loss of generality, fix a permutation of $S$: ($s_1, \ldots, s_{\alpha}, \ldots,s_{\beta}, \ldots, s_k)$ where $rank(s_{\alpha})>rank(s_{\beta}), 1\le \alpha < \beta \le k$. This permutation  induces
 a  directed spanning tree  on $S$ in the following sense: $s_1$ is the root and  any other node $s_\alpha$ ($1 < \alpha \le k$) connects to a node in the totally (strictly) ordered set $\{s_1, \dots, s_{\alpha-1}\}$ (as fixed by the above permutation).
 For convenience, we denote the event that a node $s$ connects to a node on a directed  tree $T$ as ``$s\triangleright T$.'' Note that ``$s\triangleright T$'' indicates that $s$'s rank is less than the rank of the node to which it connects. Also, we denote  the event of a directed spanning tree $T_h$ being induced on the totally (strictly) ordered set $\{s_1,s_2,\dots, s_{\alpha},\ldots,s_h\}$ as $\omega(T_h)$. The node $s_{\alpha}$ can only connect to its preceding nodes in the ordered set. Note that the directed spanning tree $T_h$ is not necessarily unique over the $h$ nodes.  Clearly, the event $\omega(T_h)$ and the event $\left(\omega(T_1) \cap (s_2\triangleright T_1)\cap(s_3\triangleright T_2)\cap\dots\cap(s_h\triangleright T_{h-1})\right)$ are equivalent\footnote{Events $A$ and $B$ in a random experiment are said to be equivalent if the probability of the symmetric difference is 0: $\Pr((A\backslash B)\cup (B\backslash A))=\Pr(A\backslash B)+\Pr(B\backslash A)=0$. Also, equivalent events have the same probability: if $A$ and $B$ are equivalent then $\Pr(A)=\Pr(B)$}. As a special case, $\omega(T_1)$ is the event of the induced directed tree $T_1$ containing only the root node $s_1$ and $\Pr(\omega(T_1))=1$.
 %In general, $T_h := T_1 \cap (u_2\triangleright T_1)\cap\dots\cap(u_h\triangleright T_{h-1}) $
 %
 % the idea of ``oder set'' is to give the order of nodes by the order their ranking to avoid confusion on nodes and ranks.
 %the ideas of ``strict total order'' and ``spanning'' directed tree ensure that a directed tree is always rooted at node u_1 (since u_1 is always of the largest rank and a directed edge only connects from a node of lower rank to a node of higher rank) and then incrementally grows up by adding nodes
 %
 %Hence, $i \triangleright T_h$ indicates that the node $i$ connects to any node in a directed tree $T_h$ induced on $\{1,2,\ldots , h\}$.
 We are interested in the event $\omega(T_k)$, i.e., a directed spanning tree $T_k$ is constructed on the set $S$ of $k$ nodes in the above fashion.
 In the following, we bound the probability of the event $\omega(T_k)$ occurring:
 \begin{align}
  \Pr(\omega(T_k))=&\Pr\left(\omega(T_1) \cap (s_2 \triangleright T_1) \cap (s_3 \triangleright T_2)  \cap \dots \cap (s_k \triangleright T_{k-1})\right) \nonumber\\
 =& \Pr(\omega(T_1)) \Pr(s_2 \triangleright T_1 |\; \omega(T_1)) \Pr(s_3 \triangleright T_2 |\, \omega(T_2)) \dots \nonumber\\ 
 &\dots \Pr(s_k \triangleright T_{k-1}|\; \omega(T_{k-1})).
 \label{eq:prob_of_tree}
\end{align}
 To bound each of the terms in the product, we  use the principle of deferred decisions~\cite{random-alg-book,random-alg-book-motwani}: when a new node is sampled (i.e., for the first time) we assign it a random rank. For simplicity, we assume that each node sampled is a new node --- this does not change the asymptotic bound, since there are now only $k = O(\log n)$ nodes under consideration and each node samples at most $O(\log n)$  nodes. This assumption allows us to use the principle of deferred decisions to assign random ranks  without worrying about sampling an already sampled node. Below we bound the conditional probability $\Pr( s_{\alpha}\triangleright T_{\alpha-1} |\; \omega(T_{\alpha-1}))$, for any $2 \leq \alpha \leq k$ as follows. Let $r_{q}=rank(s_{q})$ be the rank of node $s_{q}$, $1\le q \le \alpha$; then
  \begin{align*}
 \Pr&( s_{\alpha}\triangleright T_{\alpha-1} |\; \omega(T_{\alpha-1})) \\
 &\leq  \int_0^ 1 \int_0^{r_1}\int_0^{r_2} \dots \int_0^{r_{\alpha -1}}\; \sum_{h=1}^{\log n - 1} \left(\frac{\alpha -1}{n}\right)r^{h-1}_{\alpha} \; dr_{\alpha} \dots dr_1.
 \end{align*}
%$$\Pr( s_{\alpha}\triangleright T_{\alpha-1} |\; T_{\alpha-1})
% \leq  \int_0^ 1 \int_0^{r_1}\int_0^{r_2} \dots \int_0^{r_{\alpha -1}}\; \sum_{h=0}^{\log n - 1} \left(\frac{\alpha -1}{n}\right)r^h_{\alpha} \; dr_{\alpha} \dots dr_1.$$
 The explanation for the above bound is as follows: Since $T_{\alpha -1}$ is a directed spanning tree on the first
 $\alpha -1$ nodes, and $s_{\alpha}$ connects to $T_{\alpha - 1}$, we have $r_1 > r_2 > \dots > r_{\alpha - 1} > r_{\alpha}$.  Hence $r_1$ can take any value between 0 and 1,
 $r_2 $ can take any value between 0 and $r_1$ and so on. This is captured by the respective ranges of the integrals.
 The term inside the integrals is explained as follows.
 There  are at most $\log n- 1$ attempts for node $s_{\alpha}$  to connect to any one of the first $\alpha - 1$ nodes. Suppose it connects in the $h$-th attempt. Then, the first
 $h-1$ attempts should connect to nodes whose rank should be less than $r_{\alpha}$, hence the term $r_{\alpha}^h$ \footnote{As mentioned earlier, we assume that we do not sample an already sampled node, this does not change the bound asymptotically.}.
 The term $(\alpha -1)/n$ is the probability that $s_{\alpha}$ connects to any one of the first $\alpha - 1$ nodes in the $h$th attempt.
Simplifying the right hand side, we have,
% \begin{align*}
% \Pr&( s_{\alpha}\triangleright T_{\alpha-1} |\; T_{\alpha-1}) \\
% & \leq \frac{{\alpha}-1}{n} \int_0^ 1 \int_0^{r_1}\int_0^{r_2} \dots \int_0^{r_{{\alpha}-1}} [1 + r_{\alpha} + r_{\alpha}^2 + \dots r_{\alpha}^{\log n - 1}]  dr_{\alpha} \dots dr_1  \\
%&= \frac{{\alpha}-1}{n} \left( \frac{0!}{{\alpha}!} +  \frac{1!}{({\alpha}+1)!} + \frac{2!}{({\alpha}+2)!} + \dots + \frac{(\log n)!}{(\log n + {\alpha})!}\right).
%\end{align*}
%
\begin{align*}
 &\Pr\left( s_{\alpha}\triangleright T_{\alpha-1} |\; \omega(T_{\alpha-1})\right) \\
 & \leq \frac{{\alpha}-1}{n} \int_0^ 1 \int_0^{r_1}\int_0^{r_2} \dots \int_0^{r_{{\alpha}-1}}  \sum_{h=1}^{\log n - 1} r^{h-1}_{\alpha} \;\; dr_{\alpha} \dots dr_1 \\
& \leq \frac{{\alpha}-1}{n} \left( \frac{0!}{{\alpha}!} +  \frac{1!}{({\alpha}+1)!} + \frac{2!}{({\alpha}+2)!} + \dots + \frac{(\log n)!}{(\log n + {\alpha})!}\right).
\end{align*}
The above expression is bounded by
$\frac{b}{n}$,
where $0< b <1$ if ${\alpha} > 2$ and $0< b \leq (1 - \frac{1}{\log n + 2})$ if $\alpha = 2$.
Besides, $\Pr(T_1) \leq \frac{1}{\log n}$ (cf. Theorem~\ref{le:numtrees});
hence, the equation~(\ref{eq:prob_of_tree}) is bounded by
$\left(\frac{b}{n} \right)^{k-1} \frac{1}{\log n}.$

Using the above, the probability that a tree of size $k = c\log n$ is produced by the DRR algorithm is bounded by
\begin{align*}
%{n \choose k} k! (\frac{b}{n})^{k-1}\frac{1}{\log n}
\binom{n}{k} k! (\frac{b}{n})^{k-1}\frac{1}{\log n}
&\leq \frac{(ne)^k}{k^k} O(\sqrt{k}) \frac{k^k}{e^k} (\frac{b}{n})^{k-1}\frac{1}{\log n} \\
& \leq \frac{c' \cdot n}{\log ^{\frac{1}{2}}n} \cdot b^{k-1} \\
& \leq \frac{c'}{b^2\log ^{\frac{1}{2}}n} \cdot n^{1+ c\log b} = o(1/n),
\end{align*}
if  $c$ sufficiently large.
\endproof

\bigskip

%\vspace*{-0.1in}
%\subsubsection{Complexity of the DRR algorithm}
%\vspace*{-0.05in}
\noindent {\bf Complexity of Phase I --- the DRR algorithm}
%\vspace*{-0.05in}
\begin{thm}
The message complexity of the DRR algorithm is $O(n \log \log n)$ whp. The time complexity is $O(\log n)$ rounds.
\end{thm}

%\vspace*{-0.1in}
\proof
Let $d = \log n -1$.
Fix a node $i$. Its
 rank is chosen uniformly at random from $[0,1]$.
The expected number of nodes sampled before a node $i$ finds a higher ranked node (or else,  all $d$ nodes will be sampled)
is computed as follows.
The probability that exactly $k$ nodes will be sampled is $\Theta(\frac{1}{k+1}\frac{1}{k})$, since
the last node sampled should be the highest ranked node and $i$ should be the second highest ranked node (whp, all the nodes sampled will be unique).
Hence the expected number of nodes  probed  is
$\sum_{k = 1}^{d} \Theta\left(k \frac{1}{k+1}\frac{1}{k}\right) = O(\log d)$ 
and the expected number of messages exchanged by node $i$ is $O(\log d)$.
By linearity of expectation, the expected total number of messages exchanged by all nodes
is $O(n \log d) = O(n \log \log n)$.

To show concentration, we set up a Doob martingale~\cite{random-alg-book} as follows. Let $X$ denote the random variable that counts the
total number of nodes sampled by all nodes. $E[X] = O(n \log d)$. Assume that ranks have already been assigned to the nodes. Number the nodes according to the order statistic of their ranks: the $i$th node is the node with
the $i$th smallest rank.
Let the indicator r.v.  $Z_{ik}$  ($1 \leq i \leq n$, $1 \leq k \leq d$)  indicate whether the $k$th sample by the $i$th {\em smallest ranked}  node succeeded or not (i.e., it found
a higher ranked node).  If it succeeded then $Z_{ij} = 1$ for all $j \leq k$ and $Z_{ij} = 0$ for all $j > k$.
Thus $X = \sum_{i = 1}^n \sum_{k =1}^d Z_{ik}$.
Then  the sequence $X_0 = E[X], X_1 = E[X|Z_{11}], \dots,  X_{nd} = E[X|Z_{11}, \dots, Z_{nd}]$ is a Doob  martingale. Note that $|X_{\ell} - X_{\ell-1}| \leq d$ ($1 \leq \ell \leq nd$) because fixing the outcome of a sample of one node affects only
the outcomes of other samples made by the same node and not the samples made by other nodes.
Applying Azuma's inequality, for a positive constant $\epsilon$ we have:
$$\Pr(|X-E[X]| \geq \epsilon n) \leq 2 \exp\left(-\frac{\epsilon^2 n^2}{2 n (\log n)^3}\right) = o(1/n).$$

The time complexity is immediate since each node probes at most $O(\log n)$ nodes in as many rounds.
\endproof

%%------------- algorithm convergecast-max
\begin{algorithm}[t]
\label{alg:convergecast-max}
%\dontprintsemicolon % for Miktex previous versions
\dontprintsemicolon  % for Miktex 2.8
\caption{$\mathbf{cov}_{max}=$convergecast-max($\mathbb{F}$,$\mathbf{v}$)}
%\REQUIRE
\KwIn{The forest $\mathbb{F}$, and the value vector $\mathbf{v}$ over all nodes in $\mathbb{F}$}
\KwOut{The local $Max$ aggregate vector $\mathbf{cov}_{max}$ over all the roots}
\lForEach{leaf node}{send its value to its parent\;}
\ForEach{intermediate node}
 {
  - collect values from its children\;
  - compare collected values with its own value\;
  - update its value to the maximum amid all and send the maximum to its parent.
 }
\ForEach{root node $z$}
 {
 - collect values from its children\;
 - compare collected values with its own value\;
 - update its value to the local maximum value $\mathbf{cov}_{max}(z)$.
% \item sends the local maximum value downward along the tree to all its off-spring nodes. %for robust computation when link failure
}
\end{algorithm}
\begin{algorithm}[!ht]
\label{alg:convergecast-sum}
%\dontprintsemicolon % for Miktex previous versions
\dontprintsemicolon  % for Miktex 2.8
\caption{$\mathbf{cov}_{sum}=$convergecast-sum($\mathbb{F}$,$\mathbf{v}$)}
\KwIn{
The forest $\mathbb{F}$ and the value vector $\mathbf{v}$ over all nodes in $\mathbb{F}$}
\KwOut{The local $Sum$ aggregate vector $\mathbf{cov}_{sum}$ over all the roots.}
{\bf Initialization}: every node $i$ stores a row vector $(v_i, w_i=1)$ including its value $v_i$ and a size count $w_i$\;% indicating the number of nodes in its sub-branch along the tree.
\ForEach{leaf node $i \in \mathbb{F}$}
{- send its parent a message containing the vector $(v_i, w_i=1)$\;
 - reset $(v_i, w_i)=(0,\,0)$.}
\ForEach{intermediate node $j \in \mathbb{F}$}{
 - collect messages (vectors) from its children\;
 - compute and update $v_j=v_j+\sum_{k\in Child(j)}v_k,$ and $w_j=w_j+\sum_{k\in Child(j)}w_k,$ where $Child(j)=\{\text{$j$'s children nodes}\}$\;
 - send computed $(v_j, w_j)$ to its parent\;
 - reset its vector $(v_j, w_j)=(0,\,0)$ when its parent successfully receives its message.
 }
\ForEach{root node $z \in \tilde{V}$}{
 - collect messages (vectors) from its children\;
 - compute the local $Sum$ aggregate
$\mathbf{cov}_{sum}(z,1)=v_z+\sum_{k\in Child(z)}v_k,$ and the size count of the tree $\mathbf{cov}_{sum}(z,2)=w_z+\sum_{k\in Child(z)}w_k,$ where $Child(z)=\{\text{$z$'s children nodes}\}$.
}
\end{algorithm}

%\vspace*{-0.05in}
\subsection{Phase II: Convergecast and Broadcast}
\label{sec:phase2}
%\vspace*{-0.1in}
 In the second phase of our algorithm, the local aggregate of each tree is obtained at the root by the Convergecast algorithm --- an aggregation process starting from leaf nodes and proceeding upward along the tree to the root node. For example, to compute the local max/min, all leaf nodes simply send their values to their parent nodes. An intermediate node collects the values from its children, compares them with its own value and sends its parent node the max/min value among all received values and its own. A root node can then obtain the local max/min value of its  tree. 
%Due to space limitation, the pseudo-codes of the Convergecast algorithms for various aggregates are omitted. We refer readers to the full version of this paper~\cite{full-version} for details.  
%
 %In the pseudo-codes, the input $\mathbf{v}\in M_{n,1}$, where $M_{x,y}$ is the $x\times y$ matrix, representing the  value vector over all nodes in $V$;  the output $\mathbf{cov}_{max}\in M_{m,1}$ and $\mathbf{cov}_{sum}\in M_{m,2}$ are the computed  aggregates at root nodes, where $m$ is the number of  root nodes.

After the Convergecast process, each root broadcasts its address to all other nodes in its tree via the tree links. This process proceeds from the root down to the leaves via the tree links (these two-way links were already established during Phase 1.)
At the end of this process, all non-root nodes  know the identity (address) of their respective roots.

\bigskip
%\subsubsection{Complexity of convergecast}
\noindent {\bf Complexity of Phase II}
\begin{thm}
The message complexity of the Convergecast and Broadcast algorithms in Phase II is $O(n)$ whp. The time complexity is $O(\log n)$ rounds.
\end{thm}

\proof
Every node except the root nodes needs to send a message to its parent in the upward aggregation process of the Convergecast algorithms. So the message complexity  is $O(n)$.
 Since each node can communicate with at most one node in one round,
 the time  complexity is bounded by the size of the tree.
(This is the reason for bounding size and not just the height.)
 Since the  tree size (hence, tree height also) is bounded by $O(\log n)$ (cf. Theorem~\ref{le:sizeoftree}) the time complexity of Convergecast and Broadcast is $O(\log n)$. Moreover, the number of roots is at most $O(n/\log n)$ by Theorem~\ref{le:numtrees}; the number of non-root nodes each of which will receive a broadcast message is $n-O(n/\log n)$. Thus, the message complexity for broadcast is also $O(n)$.
\endproof
%----------------------------------------------------------------------
%----------- gossip algorithms gossip-ave/ gossip-max/ data spread
\begin{algorithm}[!ht]
\label{alg:gossip-max}
%\dontprintsemicolon % for Miktex previous versions
\dontprintsemicolon  % for Miktex 2.8
\caption{ $\mathbf{\hat{\mbx}}_{max}=$Gossip-max($G,\,\mathbb{F},\,\tilde{V},\,\mathbf{y}$)}
{\bf Initialization}: every root $i\in \tilde{V}$ is set the initial value $x_{0,i}=y(i)$ from the input $\mathbf{y}$.
\\ /* To compute $Max$, $x_{0,i}=y(i)=\mathbf{cov}_{max}(i)$;
  To compute the largest tree size (used in computing $Average$), $x_{0,i}=y(i)=\mathbf{cov}_{sum}(i,2). */$\;
{\bf Gossip procedure}:\;
\For{$t$ from 1 to $O(\log n)$ rounds}{
 Every root $i\in \tilde{V}$ independently and uniformly at random, selects a node in $V$ and sends the selected node a message containing its current value $x_{t-1,i}$.\;
 Every node $j\in V-\tilde{V}$ forwards any received messages to its root.\;
 Every root $i\in \tilde{V}$\;
 \Indp
 --- collects messages and compares the received values with its own value\;
 --- updates its current value $x_{t,i}$, which is also the $\hat{\mbx}_{max,t}(i)$, node $i$'s current estimate of $Max$, to the maximum among all received values and its own.\;
}
{\bf Sampling procedure:}\;
\For{$t$ from 1 to $\frac{1}{c}\log n$ rounds}{
Every root $i\in \tilde{V}$ independently and uniformly at random selects a node in $V$ and sends each of the selected nodes an inquiry message.\;
Every node $j\in V-\tilde{V}$ forwards any received inquiry messages to its root.\;
Every root $i\in \tilde{V}$, upon receiving inquiry messages, sends the inquiring roots its value.\;
Every root $i\in \tilde{V}$, updates $x_{t,i}$, i.e. $\hat{\mbx}_{max,t}(i)$, to the maximum value it inquires.}
\end{algorithm}
%---------------------------------------
\begin{algorithm}[!ht]
\label{alg:data-spread}
%\dontprintsemicolon % for Miktex previous versions
\dontprintsemicolon  % for Miktex 2.8
 %\vspace{.02in}\hrule \vspace{.04in}
\caption{  $\hat{\mbx}_{ru}=$Data-spread($G,\,\mathbb{F},\,\tilde{V},\,x_{ru}$)}
{\bf Initialization}: A root node $i\in \tilde{V}$ which intends to spread its value $x_{ru}$, $|x_{ru}|<\infty$ sets $x_{0,i}=x_{ru}$. All the other nodes $j$ set $x_{0,j}= \bot $.\;
Run gossip-max($G,\,\mathbb{F},\,\tilde{V},\,\mbx_0$) on the initialized values.
\end{algorithm}
%----------------------------------------------
%------------- the algorithm of gossip-ave
\begin{algorithm}[!ht] %put [!h] here can save some space.
%\begin{algorithm}[t] 
\label{alg:gossip-ave}
%\dontprintsemicolon % for Miktex previous versions
\dontprintsemicolon  % for Miktex 2.8
\caption{  $\mathbf{\hat{\mbx}}_{ave}=$Gossip-ave($G,\,\mathbb{F},\,\tilde{V},\,\mathbf{cov}_{sum}$)}%\\ (revised from Push-sum\cite{gossip})
{\bf Initialization}: Every root $i\in \tilde{V}$ sets a vector $(s_{0,i}, g_{0,i})=\mathbf{cov}_{sum}(i)$, where $s_{0,i}$ and $g_{0,i}$ are the local sum of values and the size of the tree rooted at $i$, respectively.\;
\For{$t$ from 1 to $O(\log m +\log(1/\epsilon))$ rounds}{
Every root node $i\in \tilde{V}$ independently and uniformly at random selects a node in $V$ and sends the selected node a message containing
 a row vector $(s_{t-1,i}/2, g_{t-1,i}/2)$.\;
Every node $j\in V-\tilde{V}$ forwards any received messages to the root of its  tree.\;
Let  $A_{t,i}\subseteq \tilde{V}$ be the set of roots whose messages reach root node $i$ at round $t$. Every root node $i\in \tilde{V}$ updates its row vector by\;
\Indp
 $s_{t,i}=s_{t-1,i}/2+\sum_{j\in A_{t,i}}s_{t-1,j}/2$,\;
 $g_{t,i}=g_{t-1,i}/2+\sum_{j\in A_{t,i}} g_{t-1,j}/2$.\;
\Indm
Every root node $i\in \tilde{V}$ updates its estimate of the aggregate $Average$ by $\hat{\mbx}_{ave, t}(i)=\hat{x}_{ave, t, i}=s_{t,i}/g_{t,i}$.
}
\end{algorithm}
%----------------------------------------------
%-----------------------------------------------------------------------
%\vspace*{-0.05in}
\subsection{Phase III: Gossip}
\label{sec:phase3}
%%\vspace*{-0.1in}
In the third phase, all roots of the trees compute the global aggregate by performing the gossip algorithm on the overlaying graph $\tilde{G}=clique(\tilde{V})$, where $\tilde{V}\subseteq V$ is the set of roots and $|\tilde{V}|=m = O(n/\log n)$ (cf. Theorem~\ref{le:numtrees}). 
%%%%%% the following is to address spaa reviewer 2's comment on uniform gossip
Since the trees are formed randomly, roots do not know each other's addresses. However, the gossip procedure on the roots (i.e., the nodes of $\tilde{G}$) can be implemented as described below. 
 
 In each round of the gossip procedure, every root independently and uniformly at random selects  a node in $V$ (i.e., calls a node of the graph $G$) to send  its message. If the selected node is another root then the task is completed. If not, the selected node will  {\em forward} the received message to the root of the tree it belongs to. We note that all nodes in a tree know their root's address at the end of Phase II (cf. Section \ref{sec:phase2})  ---  here is where we use a non-address oblivious communication. Thus, to traverse through an edge of $\tilde{G}$, a message needs at most two hops of $G$. 
 
% Thus, in some sense, a ranking tree becomes a super node and all the super nodes form a complete graph, %$\tilde{G}$.

%As shown in Appendix~\ref{apx:gossips},  
Algorithm~\ref{alg:gossip-max}, Gossip-max, and  Algorithm~\ref{alg:gossip-ave}, Gossip-ave (which is a modification from the  Push-Sum algorithm of~\cite{kempe})  compute $Max$ and $Average$ respectively. (Other aggregates such as $Min$, $Sum$ and $Count$ etc., can be calculated by a suitable modification as mentioned latter in Section~\ref{sec:other-aggregate}.) Note that,  in addition  to the gossip procedure,  the Gossip-max algorithm needs a sampling procedure in which every root inquires values from other roots. Similar to the gossip procedure, the sampling procedure requires the selected  node, if it is  not a root itself, to forward the inquiry message to the root of its tree. The inquiry message contains the inquiring root's address so that the inquired root can send back its value accordingly.   

Algorithm~\ref{alg:data-spread}, Data-spread, a modification of  Gossip-max,  can be  used by  a root node to spread its value. If a root needs to spread a particular value over the network, it sets this  value as its initial value  and all other roots set their initial value to $-\infty$ or the bottom value ``$\bot$'' of the system.

%
%%----------- gossip algorithms gossip-ave/ gossip-max/ data spread
%\begin{algorithm}[t]
%\label{alg:gossip-max}
%%\dontprintsemicolon % for Miktex previous versions
%\dontprintsemicolon  % for Miktex 2.8
%\caption{ $\mathbf{\hat{\mbx}}_{max}=$Gossip-max($G,\,\mathbb{F},\,\tilde{V},\,\mathbf{y}$)}
%{\bf Initialization}: every root $i\in \tilde{V}$ is set the initial value $x_{0,i}=y(i)$ from the input $\mathbf{y}$.
%\\ /* To compute $Max$, $x_{0,i}=y(i)=\mathbf{cov}_{max}(i)$;
%  To compute the largest tree size (used in computing $Average$), $x_{0,i}=y(i)=\mathbf{cov}_{sum}(i,2). */$\;
%{\bf Gossip procedure}:\;
%\For{$t$ from 1 to $O(\log n)$ rounds}{
% Every root $i\in \tilde{V}$ independently and uniformly at random, selects a node in $V$ and sends the selected node a message containing its current value $x_{t-1,i}$.\;
% Every node $j\in V-\tilde{V}$ forwards any received messages to its root.\;
% Every root $i\in \tilde{V}$\;
% \Indp
% --- collects messages and compares the received values with its own value\;
% --- updates its current value $x_{t,i}$, which is also the $\hat{\mbx}_{max,t}(i)$, node $i$'s current estimate of $Max$, to the maximum among all received values and its own.\;
%}
%{\bf Sampling procedure:}\;
%\For{$t$ from 1 to $\frac{1}{c}\log n$ rounds}{
%Every root $i\in \tilde{V}$ independently and uniformly at random selects a node in $V$ and sends each of the selected nodes an inquiry message.\;
%Every node $j\in V-\tilde{V}$ forwards any received inquiry messages to its root.\;
%Every root $i\in \tilde{V}$, upon receiving inquiry messages, sends the inquiring roots its value.\;
%Every root $i\in \tilde{V}$, updates $x_{t,i}$, i.e. $\hat{\mbx}_{max,t}(i)$, to the maximum value it inquires.}
%\end{algorithm}
%%---------------------------------------
%\begin{algorithm}
%\label{alg:data-spread}
%%\dontprintsemicolon % for Miktex previous versions
%\dontprintsemicolon  % for Miktex 2.8
% %\vspace{.02in}\hrule \vspace{.04in}
%\caption{  $\hat{\mbx}_{ru}=$Data-spread($G,\,\mathbb{F},\,\tilde{V},\,x_{ru}$)}
%{\bf Initialization}: A root node $i\in \tilde{V}$ which intends to spread its value $x_{ru}$, $|x_{ru}|<\infty$ sets $x_{0,i}=x_{ru}$. All the other nodes $j$ set $x_{0,j}= -\infty $.\;
%Run gossip-max($G,\,\mathbb{F},\,\tilde{V},\,\mbx_0$) on the initialized values.
%\end{algorithm}
%%----------------------------------------------
%%------------- the algorithm of gossip-ave
%\begin{algorithm}[!h] %put [!h] here can save some space.
%%\begin{algorithm}[t] 
%\label{alg:gossip-ave}
%%\dontprintsemicolon % for Miktex previous versions
%\dontprintsemicolon  % for Miktex 2.8
%\caption{  $\mathbf{\hat{\mbx}}_{ave}=$Gossip-ave($G,\,\mathbb{F},\,\tilde{V},\,\mathbf{cov}_{sum}$)}%\\ (revised from Push-sum\cite{gossip})
%{\bf Initialization}: Every root $i\in \tilde{V}$ sets a vector $(s_{0,i}, g_{0,i})=\mathbf{cov}_{sum}(i)$, where $s_{0,i}$ and $g_{0,i}$ are the local sum of values and the size of the tree rooted at $i$, respectively.\;
%\For{$t$ from 1 to $O(\log m +\log(1/\epsilon))$ rounds}{
%Every root node $i\in \tilde{V}$ independently and uniformly at random selects a node in $V$ and sends the selected node a message containing
% a row vector $(s_{t-1,i}/2, g_{t-1,i}/2)$.\;
%Every node $j\in V-\tilde{V}$ forwards any received messages to the root of its  tree.\;
%Let  $A_{t,i}\subseteq \tilde{V}$ be the set of roots whose messages reach root node $i$ at round $t$. Every root node $i\in \tilde{V}$ updates its row vector by\;
%\Indp
% $s_{t,i}=s_{t-1,i}/2+\sum_{j\in A_{t,i}}s_{t-1,j}/2$,\;
% $g_{t,i}=g_{t-1,i}/2+\sum_{j\in A_{t,i}} g_{t-1,j}/2$.\;
%\Indm
%Every root node $i\in \tilde{V}$ updates its estimate of the global average by $\hat{\mbx}_{ave, t}(i)=\hat{x}_{ave, t, i}=s_{t,i}/g_{t,i}$.
%}
%\end{algorithm}
%%----------------------------------------------

\subsubsection{Performance of Gossip-max and Data-spread}
%\vspace*{-0.05in}
Let $m$ denote the number of  roots. By Theorem~\ref{le:numtrees}, we have $m=|\tilde{V}|=O(n/\log n)$ where $n=|V|$. Karp et al.~\cite{Karp-rumor} show that all  $m$ nodes of a complete graph can know a particular rumor (e.g., the $Max$ in our application) in $O(\log m)=O(\log n)$ rounds with high probability
by using their Push algorithm (a prototype of our Gossip-max algorithm)  with  uniform selection probability. Similar to the Push algorithm,  Gossip-max  needs $O(m\log m)=O(n)$ messages for all  roots to obtain $Max$ if the selection probability is uniform, i.e., $1/m$.
However, in the implementation of the Gossip-max algorithm on the  forest, the root of a tree is selected with a \emph{probability proportional to its size (number of nodes in the tree)}. Hence, the selection probability is not uniform. In this case, we can only guarantee that after  the gossip procedure of the Gossip-max algorithm, a portion of the roots including the root of the largest tree will possess the $Max$. After the gossip procedure, roots can sample $O(\log n)$ other roots to confirm and update, if necessary, their values and reach consensus on the global maximum, $Max$. In the following, we discuss the performance of the Gossip-Max algorithm procedure by procedure.

\noindent {\bf Gossip Procedure}\\
We first show the following theorem for the gossip procedure of the Gossip-Max algorithm.
%\vspace*{-0.05in}
\begin{thm}\label{thm:uniform}
After the gossip procedure of the Gossip-max algorithm, at least $\Omega(\frac{c\cdot n}{\log n})$ roots obtain  the global maximum, $Max$, whp, where $n=|V|$ and $0<c<1$ is a constant. %$\rho$ is the probability that a message fails to reach its destined root.
%$\rho$ is the probability that a message fails to arrive at its destined root node.
\end{thm}
%\vspace*{-0.05in}
%
%----------------------------------------

\proof
As per our failure model, a message may fail to reach the selected root node with probability
$\rho$ (which is at most  $2\delta$, since failure may occur either during the initial call to a non-root node or during the forwarding call from the non-root node to the root of its tree).
For convenience, we call those roots who  know the $Max$  value (the global Maximum) as the max-roots and those who do not as the non-max-roots.

Let $R_t$ be the number of max-roots in round $t$.
Our proof is in two steps.
We first show that, whp, $R_t > 4\log n$ after $8\log n/(1-\rho)$ rounds of Gossip-max.
If $R_0 > 4\log n$ then the task is completed. Consider the case when $R_0 < 4\log n$.  Since the initial number of max-roots is small in this case, the probability that a max-root selects another max-root is small. Similarly, the probability that two or more max-roots select the same root is also small.  So, in this step, whp a max-root will select a non-max-root to send out its gossip message. If the gossip message successfully reaches the selected non-max-root, $R_t$ will increase by 1. Let $X_i$ denote the indicator of the event that a gossip message $i$ from some max-root successfully reaches the selected non-max-root. We have $Pr(X_i=1)=(1-\rho)$. Then $X=\sum_{i=1}^{8\log n/(1-\rho)}X_i$  is the minimal number of max-roots after $8\log n/(1-\rho)$ rounds. Clearly, $E[X]= 8\log n$. Here we conservatively assume the worst situation that initially there is only one max-root and at each round only one max-root selects a  non-max-root. So $X$ is the minimal number of max-roots after $8\log n/(1-\rho)$ rounds. For  clarity, let $\tilde{n}=8\log n/(1-\rho)$. Define a Doob martingale sequence $Z_0, Z_1, \ldots, Z_{\tilde{n}}$ by setting $Z_0=E[X]$, and, for $1\le i \le \tilde{n}$, $Z_i=E[X|X_1,\dots,X_i]$. It is clear that $Z_{\tilde{n}}=X$ and, for $1\le i \le \tilde{n}$, $|Z_i-Z_{i-1}|\le 1$.
 %In practice, instead of growing linearly, the number of max-roots can explode geometrically with constant 2 at this early %stage of the Gossip-max algorithm, making our goal, $R_t> 4 \log n$, getting achieved faster than $t=8\log n/(1-\rho)$.

Applying Azuma's inequality and setting $\epsilon=1/2$:
\begin{align*}
\Pr(|&X-E[X]|\ge \epsilon E[X])= \Pr(|Z_{\tilde{n}}-Z_0|\ge \epsilon E[X])\\ &\le 2\exp\left(-\frac{\epsilon ^2E[X]^2}{2\sum_{i=1}^{\tilde{n}}1^2} \right) = 2\exp\left(-\frac{\epsilon ^2E[X]^2}{2(\frac{8\log n}{1-\rho})} \right) \\
&%< 2\exp\left(-\frac{\frac{1}{4}E[X]^2}{16\log n} \right)
= 2\exp\left(\log n^{-(1-\rho)}\right)=2\cdot n^{-(1-\rho)},
\end{align*}
where $\rho$ could be arbitrarily small. Wlog, let $\rho < 1/4$, then $\Pr(|X-E[X]|\ge \epsilon E[X])\le 2\cdot n^{-\frac{3}{4}}$.
Hence, whp, after $8\log n/(1-\rho)=O(\log n)$ rounds, $R_t \ge R_0+X >R_0+\frac{1}{2}E[X]=R_0+4\log n > 4\log n$.

In the second step of our proof,  we  lower bound \emph{the increasing rate} of $R_t$ when $R_t>4\log n$.
In each round, there are $R_t$ messages sent out from max-roots. Let $Y_i$ denote the indicator of an event that such a message $i$ from a max-root successfully reaches a non-max-root. $Y_i=0$ when either of the following events happen:  (1)  The message $i$ fails in routing to its destination; (2)  The  message $i$ is sent  to another max-root, although it successfully travels over the network. The probability of this event is at most $((1- \rho)R_t\log n)/n$ since whp the size of a  tree is $O(\log n)$ (cf.Theorem~\ref{le:sizeoftree}).  (3) The message $i$ and at least one other message are destined to a same non-max-root. 
%As the probability of three or more messages are destined to a same node is very small, we only consider the case that two messages select the same non-max-root. 
%Comparing to the probability that a node receives only one message or two messages, the probability that a node receives three or more messages are negligibly small (less than $O(1/n^2)$) . Therefore, we only consider the case that two messages are destined to a same non-max root. 
Comparing to the probability (which is at most $((1- \rho)R_t\log n)/n$) that exactly one other message arrives at the same non-max-root picked by message $i$, the probabilities that two or more other messages choose the same non-max-root as message $i$ is negligibly small (less than $((1- \rho)(R_t\log n)/n)^2$) and does not affect our calculation asymptotically. Therefore, we only consider the case that two messages are destined to a same non-max root.     
We also conservatively exclude both these two messages on their possible contributions to the increase of $R_t$. Thus, this event happens with probability at most $((1- \rho)R_t\log n)/n$.

Applying the union bound~\cite{random-alg-book},
\begin{align*}
\Pr(Y_i=0)\leq \rho + \frac{2(1- \rho)R_t\log n}{n}.
\end{align*}
Since $R_t\le \frac{c n}{\log n}$ for any constant $0<c<1$ (otherwise, the task is completed),
%\begin{align*}
\(
\Pr(Y_i=0)\leq \rho +  2c(1- \rho)=c'+(1-c')\rho,
\)
%\end{align*}
where $c'=2c<1$ is a constant that is suitably fixed so that $c'+(1-c')\rho <1$. Consequently, we have
%\begin{align*}
\(\Pr(Y_i=1)> (1-c')(1-\rho),\)
%\end{align*}
and
%\begin{align*}
\(E[Y]=\sum_{i=1}^{R_t}E[Y_i] > (1-c')(1-\rho)R_t.\)
%\end{align*}

Applying Azuma's inequality as before,
\begin{align*}
\Pr(|Y-E[Y]|&>\epsilon E[Y]) < 2\exp\left( -\frac{\epsilon^2 E[Y]^2}{2R_t}\right)\\
&< 2\exp\left( -\frac{\epsilon^2(1-c')^2(1-\rho)^2R_t}{2} \right).
\end{align*}
Since in this step, whp $R_t>4\log n$, and $(1-c')^2(1-\rho)^2>0$, setting $\epsilon =\frac{1}{2}$ and $\alpha = O(1)$, we obtain
\begin{align*}
\Pr(Y<\frac{1}{2}(1-c')(1-\rho)R_t) < 2\cdot n^{-\alpha}.
\end{align*}
Thus, whp,
\(R_{t+1} > R_t+ \frac{1}{2}(1-c')(1-\rho)R_t=\beta R_t,\)
where $ \beta=1+ \frac{1}{2}(1-c')(1-\rho) >1$.
Therefore, whp, after $(8\log n/(1-\rho)+\log_{\beta}n)=O(\log n)$ rounds, at least $\Omega(\frac{c\cdot n}{\log n})$ roots will have the $Max$.
\endproof
%
%-------------------------------------------------
%
%
%
%\subsubsection{Sampling Procedure}

\noindent {\bf Sampling Procedure}

From Theorem~\ref{thm:uniform}, after the gossip procedure, there are $\Omega(\frac{c n}{\log n})=\Omega(c m)$, $0<c<1$ roots with the $Max$ value.
For  all roots to reach  consensus on $Max$,   they sample each other as in the sampling procedure.
It is possible that the root of a larger  tree will be sampled more frequently than the roots of smaller trees.  However, this non-uniformity is an advantage, since the roots of larger trees would have obtained  $Max$ (in the gossip procedure) with higher probability due to this same non-uniformity. Hence, in  the sampling procedure, a root without $Max$ can obtain $Max$ with higher probability by this non-uniform sampling.
Thus, we have the following theorem.
%
%\vspace*{-0.1in}
\begin{thm}\label{thm:sampling}
After the sampling procedure of  Gossip-max algorithm, all  roots know the $Max$ value, whp.
\end{thm}

%\vspace*{-0.1in}
\proof
After the sampling procedure, the probability that none of the roots possessing the $Max$ is sampled by a root not knowing the $Max$ is at most
%\[\left(\frac{\frac{n}{\log n}-\frac{c n}{\log n}}{\frac{n}{\log n}}\right)^{\frac{1}{c}\log n}<\frac{1}{n}.\]
\(\left(\frac{m - cm}{m}\right)^{\frac{1}{c}\log n}<\frac{1}{n}.\)
Thus, after the sampling procedure, with probability at least $1-\frac{1}{n}$, all the roots will know the $Max$.
%(For a higher probability such as $1-\frac{1}{n^b}$, just sample $\frac{b}{c}\log n$ other roots.)
\endproof
%
%A root could further pass the $Max$ downward to other nodes in its ranking tree.
%\noindent \textbf{Complexity of Gossip-max}\\

\noindent {\bf Complexity of the Gossip-max and  Data-spread algorithms}
\begin{thm}\label{thm:complexity-gossip-max} 
The Gossip-max algorithm totally takes $O(\log n)$ rounds and $O(n)$ messages for all the roots in the network to reach consensus on $Max$.
\end{thm}

\proof
In the Gossip-max algorithm, the gossip procedure takes $O(\log n)$ rounds and $O(m\log n)=O(n)$ messages. The sampling procedure takes $O(\frac{1}{c}\log n)$$=$$O(\log n)$ rounds and $O(\frac{m}{c}\log n)=O(n)$ messages.
%To forward $Max$ to member nodes in a ranking tree takes $O(\log n)$ rounds and $O(n)$ messages.
To sum up,  the Gossip-max algorithm totally takes $O(\log n)$ rounds and $O(n)$ messages for all the roots in the network to reach consensus on $Max$.
\endproof
The complexity of the Data-spread algorithm is the same as the Gossip-max algorithm.
%
%
%
%\vspace*{-0.05in}

%%------------- the algorithm of gossip-ave
%%\begin{algorithm}[!ht] %put [!h] here can save some space.
%\begin{algorithm}[t] 
%\label{alg:gossip-ave}
%%\dontprintsemicolon % for Miktex previous versions
%\dontprintsemicolon  % for Miktex 2.8
%\caption{  $\mathbf{\hat{\mbx}}_{ave}=$Gossip-ave($G,\,\mathbb{F},\,\tilde{V},\,\mathbf{cov}_{sum}$)}%\\ (revised from Push-sum\cite{gossip})
%{\bf Initialization}: Every root $i\in \tilde{V}$ sets a vector $(s_{0,i}, g_{0,i})=\mathbf{cov}_{sum}(i)$, where $s_{0,i}$ and $g_{0,i}$ are the local sum of values and the size of the tree rooted at $i$, respectively.\;
%\For{$t$ from 1 to $O(\log m +\log(1/\epsilon))$ rounds}{
%Every root node $i\in \tilde{V}$ independently and uniformly at random selects a node in $V$ and sends the selected node a message containing
% a row vector $(s_{t-1,i}/2, g_{t-1,i}/2)$.\;
%Every node $j\in V-\tilde{V}$ forwards any received messages to the root of its  tree.\;
%Let  $A_{t,i}\subseteq \tilde{V}$ be the set of roots whose messages reach root node $i$ at round $t$. Every root node $i\in \tilde{V}$ updates its row vector by\;
%\Indp
% $s_{t,i}=s_{t-1,i}/2+\sum_{j\in A_{t,i}}s_{t-1,j}/2$,\;
% $g_{t,i}=g_{t-1,i}/2+\sum_{j\in A_{t,i}} g_{t-1,j}/2$.\;
%\Indm
%Every root node $i\in \tilde{V}$ updates its estimate of the global average by $\hat{\mbx}_{ave, t}(i)=\hat{x}_{ave, t, i}=s_{t,i}/g_{t,i}$.
%}
%\end{algorithm}
%%-------------

\subsubsection{Performance of  Gossip-ave}
When the uniformity assumption holds in gossip (i.e., in each round, nodes are selected uniformly at random),  it has been shown in~\cite{kempe} that on an $m$-clique with probability at least $1-\delta'$, Gossip-ave (uniform push-sum in~\cite{kempe}) needs $O(\log m+\log \frac{1}{\epsilon}+\log \frac{1}{\delta'})$ rounds and $O(m(\log m+\log \frac{1}{\epsilon}+\log \frac{1}{\delta'}))$ messages for all  $m$ (root) nodes to reach consensus on the average within a relative error of at most $\epsilon$.
When  uniformity  does not hold, the performance of uniform gossip will depend on the distribution of  selection probability. In the efficient gossip algorithm~\cite{efficient-gossip}, it is shown that the root being selected with the largest probability will have the global average, $Average$, in $O(\log m + \log \frac{1}{\epsilon})$ rounds. Here, we show in Theorem~\ref{thm:gossip-ave-upper-bound} that the same upper bound holds for our Gossip-ave algorithm, namely,  the root of the largest tree  will have $Average$ after $O(\log m + \log \frac{1}{\epsilon})$ rounds of the gossip procedure of  Gossip-ave algorithm. In this bound, $m=O(n/\log n)$ is the number of roots (obtained from the DRR algorithm) and the relative error $\epsilon = n^{-\alpha },\,\alpha >0$.
%Thus, the root of the largest tree  will have $Average$ after $O(\log m + \log \frac{1}{\epsilon})=O(\log n)$ rounds of the gossip procedure.
%The upper bound of the running time of the Gossip-ave algorithm is given by the following theorem (proof in Appendix.)
%%%%

%\vspace*{-0.1in}
\begin{thm}\label{thm:gossip-ave-upper-bound}
Whp, there exists a time $T_{ave}=O(\log m +\alpha \log n)=O(\log n)$, $\alpha >0$, such that for all time $t\ge T_{ave}$, the relative error of the estimate of $Average$ on the root of the largest tree, $z$, is at most $\frac{2}{n^{\alpha}-1}$, where the relative error is $\frac{|\hat{x}_{ave, t, z}-x_{ave}|}{|x_{ave}|}$, and the value of $Average$ is $x_{ave}=\frac{\sum_{i} v_i}{n}$. 
%(assuming all $x_j$ have the same sign).   
\end{thm}
%JY
%modify the first sentence  1/12
%
(This theorem will be proved later.)

We recall that the gossip-ave algorithm works on the graph $\tilde{G}=clique(\tilde{V})$, where $\tilde{V}\subseteq V$ is the set of roots and $|\tilde{V}|= m = O(n/\log n)$.
To prove Theorem~\ref{thm:gossip-ave-upper-bound},
we need some definitions as in~\cite{kempe}.  We define a $m$-tuple contribution vector $\mathbf{y}_{t,i}$ such that $s_{t,i}=\mathbf{y}_{t,i}\cdot \mbx=\sum_{j} y_{t,i,j}x_{j}$ and $w_{t,i}=\|\mby_{t,i}\|_1=\sum_j y_{t,i,j}$,
where $y_{t,i,j}$ is the $j$-th entry of $\mathbf{y}_{t,i}$ and $x_j$ is the initial value at root node $j$, i.e., $x_j=\mathbf{cov}_{sum}(j)$ , the local aggregate of the tree rooted at node $j$ computed by Convergecast-sum.  $\mby_{0,i}=e_i$, the unit vector with the $i$-th entry being  1. Therefore, $\sum_{i} y_{t,i,j}=1$, and $\sum_{ i} w_{t,i}=m$. When $\mby_{t,i}$ is close to $\frac{1}{m}\mathbf{1}$,  where $\mathbf{1}$ is the vector with all entries 1, the approximate value of $Average$ at time $t$, $\hat{x}_{ave, t, i}=\frac{s_{t,i}}{g_{t,i}}$, is close to the true value of   $Average$, $x_{ave}$. Note that $w_{t,i}$, which is different from $g_{t,i}$, is a dummy parameter borrowed from~\cite{kempe} to characterize the diffusion speed.

In our Gossip-ave algorithm, we set $g_{0,i}$ to be the size of the root $i$'s  tree. The algorithm then computes the estimate of $Average$ directly by $\hat{x}_{ave, t, i}=s_{t,i}/g_{t,i}$. If we set a dummy weight $w_{t,i}$, whose initial value $w_{0,i}=1,\,\forall i \in \tilde{V}$, the algorithm performs in the same manner: every node works on a triplet $(s_{t,i}, g_{t,i},w_{t,i})$ and computes $\hat{x}_{ave, t, i}=\frac{(s_{t,i}/w_{t,i})}{(g_{t,i}/w_{t,i})}$.  $(s_{t,i}/w_{t,i})$ is the estimate of the average local sum on a root and  $g_{t,i}/w_{t,i}$ is the estimate of the average size of a  tree. Their relative errors are bounded in the same way as follows.

The relative error in the contributions (with respect to the diffusion effect of gossip) at node $i$ at time $t$ is $\Delta_{t,i}=\max_j |\frac{y_{t,i,j}}{\|\mathbf{y}_{t,i}\|_1}-\frac{1}{m}|=\|\frac{\mathbf{y}_{t,i}}{\|\mathbf{y}_{t,i}\|_1}-\frac{1}{m}\cdot \mathbf{1}\|_{\infty}$.
The following potential function
$$\Phi_{t}=\sum_{i,j}(y_{t,i,j}-\frac{w_{t,i}}{m})^2$$
is the sum of the variance of the contributions $y_{t,i,j}$. Let $z$ be the root of the largest tree.
% (in terms of the number of nodes in the tree),

%For the upper bound of the running time of the Gossip-ave algorithm, we have the following theorem.
%\begin{thm}\label{thm:gossip-ave-upper-bound}
%Whp, there exists a time $T_{ave}=O(\log m +\alpha \log n)=O(\log n)$,$\alpha >0$, such that for all time $t\ge T_{ave}$, the relative error of the estimate of average aggregate on the root of the largest ranking tree, $z$, is at most $\frac{2}{n^{\alpha}-1}$, where the relative error is $\frac{|\hat{x}_{ave, t, z}-x_{ave}|}{|x_{ave}|}$ and the global $Average$ is $x_{ave}=\sum_{j} x_j$, when all $x_j$ have the same sign\footnote{We can always offset the values to have the same sign.}.
%\end{thm}

To prove Theorem~\ref{thm:gossip-ave-upper-bound}, we need some auxiliary lemmas.

\begin{lem}[Geometric convergence of $\Phi$]\label{lem:gossip-convergence rate}
The conditional expectation 
\begin{center}
$E[\Phi_{t+1}|\Phi_{t}=\phi]=\frac{1}{2}(1-\sum_{i\in \tilde{V}} P_i^2)\phi<\frac{1}{2}\phi$
\end{center}
where $P_i=(1-\delta)\frac{g_i}{n}$ is the probability that the root node $i$ is selected by any other root node, $g_i$ is the size of the tree rooted at node $i$, $\delta$ is the probability that a message fails to reach its destined root node, and $n$ is the total number of nodes in the network.
\end{lem}
%A similar lemma for the particular algorithm in~\cite{efficient-gossip} is presented in~\cite{efficient-gossip} without proof.
%\vspace*{-0.1in}
%
%proof of lemma move to appendix
%
%
%-----------------------
%

\proof
This proof is generalized from~\cite{kempe}. The difference is that the selection probability, $P_i$, is not uniform any more but depends on the tree size, $g_i$.
 $P_i$ is the probability that root $i$ is selected by any other root and $\sum_{i\in \tilde{V}}P_i^2$ is the probability that two roots select the same root.
The conditional expectation of potential at round $t+1$ is
\begin{align*}
E[&\Phi_{t+1}|\Phi_{t}=\phi]\\
&=
%\begin{split}
\frac{1}{2}\phi +\frac{1}{2}\sum_{i,j,k}\left( y_{i,j}-\frac{w_{i}}{m}\right)\left(y_{k,j}-\frac{w_{k}}{m}\right)P_i\\
&\quad +\frac{1}{2}\sum_{j,k}\sum_{k'\neq k}\left( y_{k,j}-\frac{w_{k}}{m}\right)\left(y_{k',j}-\frac{w_{k'}}{m}\right)\sum_{i\in \tilde{V}}P_i^2\\
%\end{split}
&=
%\begin{split}
\frac{1}{2}\phi +\frac{1}{2}\sum_{i,j,k}\left( y_{i,j}-\frac{w_{i}}{m}\right)\left(y_{k,j}-\frac{w_{k}}{m}\right)P_i\\
&\quad +\frac{\sum_{i\in \tilde{V}}P_i^2}{2}\sum_{k,j,k'}\left( y_{k,j}-\frac{w_{k}}{m}\right)\left(y_{k',j}-\frac{w_{k'}}{m}\right)\\
&\quad -\frac{\sum_{i\in \tilde{V}}P_i^2}{2}\sum_{k,j}\left( y_{k,j}-\frac{w_{k}}{m}\right)^2\\
%\end{split}
&=\frac{1}{2}(1-\sum_{i\in \tilde{V}}P_i^2)\phi \\
&\quad +\frac{1}{2}\sum_{i,j}(P_i+\sum_{i\in \tilde{V}}P_i^2)\left( y_{i,j}
 -\frac{w_{i}}{m}\right)\sum_{k}\left( y_{k,j}-\frac{w_{k}}{m}\right)\\
&=\frac{1}{2}(1-\sum_{i\in \tilde{V}}P_i^2 )\phi
<\frac{1}{2}\phi.
\end{align*}
The last equality follows from the fact that

\begin{center}
$\sum_{k}\left( y_{k,j}-\frac{w_{k}}{m}\right)=\sum_{k} y_{k,j}- \sum_{k}\frac{w_{k}}{m}=1-1=0.$
\end{center}
\endproof
%

%
%
%
%---------------------
\begin{lem}\label{lem:lower-bound-weight}
There exists a $\tau=O(\log m)$ such that after $\forall t>\tau$ rounds of Gossip-ave, $w_{t,z}\geq 2^{-\tau}$ at $z$, the root of the largest tree.
\end{lem}
%(This lemma and its proof are inspired by~\cite{kempe,efficient-gossip}.)
%\vspace*{-0.1in}

\proof
 In the case that the selection probability is  uniform, it has been shown in~\cite{kempe}  that on an $m$-clique, with probability at least $1-\frac{\delta'}{2}$, after $4\log m +\log {2}{\delta'}$ rounds, a message originating from any node (through a random walk on the clique) would have  visited all nodes of the clique. When the distribution of the selection probability is not uniform, it is clear that a message originating from any node must have visited the node with the highest selection probability  after a certain number of rounds that is greater than $4\log m +\log {2}{\delta'}$ with probability at least $1-\frac{\delta'}{2}$.
\endproof

From the previous two lemmas, we derive the following lemma.
% which is extended from the Theorem 2.1 of~\cite{kempe}.  While Theorem 2.1 of~\cite{kempe} is to show the diffusion speed by which all the nodes of a complete graph will obtain the $Average$ under uniform selection probability, our theorem guarantees the root node $z$ of the largest ranking tree will have $Average$ after a certain time under non-uniform selection probability of the Gossip-ave algorithm.

\begin{lem}[Diffusion speed of Gossip-ave]\label{thm:diffusion-speed}
With probability at least $1-\delta'$, there exists a time $T_{ave}=O(\log m +\log \frac{1}{\epsilon} +\log \frac{1}{\delta'})$, such that $\forall t \ge T_{ave}$, the contributions at  $z$, root of the largest tree, is nearly uniform, i.e.,
$\max_j|\frac{y_{t,z,j}}{\|\mby_{t,z}\|_1}-\frac{1}{m}|=\|\frac{\mathbf{y}_{t,i}}{\|\mathbf{y}_{t,i}\|_1}-\frac{1}{m}\cdot \mathbf{1}\|_{\infty} \le \epsilon$.
\end{lem}
\proof
By Lemma~\ref{lem:gossip-convergence rate}, we obtain that $E[\Phi_t]<(m-1)2^{-t}<m2^{-t}$, as $\Phi_0=(m-1)$. By Lemma~\ref{lem:lower-bound-weight}, we set $\tau=4\log m +\log \frac{2}{\delta'}$ and $\hat{\epsilon}^2=\epsilon^2\cdot \frac{\delta'}{2}\cdot 2^{-2\tau}$. Then after
$t=\log m + \log \frac{1}{\hat{\epsilon}}$ rounds of Gossip-ave,  $E[\Phi_t]\le \hat{\epsilon}$. By Markov's inequality~\cite{random-alg-book}, with probability at least $1-\frac{\delta'}{2}$, the potential $\Phi_t\le \epsilon^2\cdot 2^{-2\tau}$, which guarantees that $|y_{t,i,j}-\frac{w_{t,i}}{m}|\le \epsilon \cdot 2^{-\tau}$ for all the root nodes $i$.

To have  $\max_j|\frac{y_{t,z,j}}{\|\mby_{t,z}\|_1}-\frac{1}{m}|\le \epsilon$, we need to lower bound  the weight of node $z$. From Lemma~\ref{lem:lower-bound-weight}, $w_{t,z}=\|\mby_{t,z}\|_1\geq 2^{-\tau}$ with probability at least $1-\frac{\delta'}{2}$. Note that Lemma~\ref{lem:lower-bound-weight} only applies to  $z$, the root of the largest tree. (A root node of a relatively small  tree may not be selected often enough to have such a lower bound on its weight.)
Using the union bound, we obtain, with probability at least $1-\delta'$,
\(\max_j|\frac{y_{t,z,j}}{\|\mby_{t,z}\|_1}-\frac{1}{m}|\le \epsilon.\)
\endproof
Now we are ready to prove Theorem~\ref{thm:gossip-ave-upper-bound}.\\
\textbf{Proof of Theorem~\ref{thm:gossip-ave-upper-bound}}\\
For convenience, we restate Theorem~\ref{thm:gossip-ave-upper-bound}:\\
{\it
Whp, there exists a time $T_{ave}=O(\log m +\alpha \log n)=O(\log n)$, $\alpha >0$, such that for all time $t\ge T_{ave}$, the relative error of the estimate of $Average$ on the root of the largest tree, $z$, is at most $\frac{2}{n^{\alpha}-1}$, where the relative error is $\frac{|\hat{x}_{ave, t, z}-x_{ave}|}{|x_{ave}|}$, and the value of $Average$ is $x_{ave}=\frac{\sum_{i} v_i}{n}$. 
%(assuming all $x_j$ have the same sign).   
}

\proof
From Lemma~\ref{thm:diffusion-speed}, with probability at least $1-\delta'$, it is guaranteed that after $T_{ave}=O(2\log m +\log \frac{1}{\epsilon} +\log \frac{1}{\delta'})$ rounds of Gossip-ave, at  $z$, the root of the largest tree, $\|\frac{\mathbf{y}_{t,i}}{\|\mathbf{y}_{t,i}\|_1}-\frac{1}{m}\cdot \mathbf{1}\|_{\infty}\le \frac{\epsilon}{m}$.
Let both $\epsilon= n^{-\alpha}$ and $\delta'= n^{-\alpha}, \;\alpha >0$, then $T_{ave}=O(2\log m + 2\alpha \log n)=O(\log n)$.

Using  H\"{o}lder's inequality~\cite{inequality-book,random-alg-book-motwani}, we obtain
\begin{align*}
&\frac{\left|\frac{s_{t,z}}{w_{t,z}}-\frac{1}{m}\sum_j x_j\right|}{\left|\frac{1}{m}\sum_j x_j\right|}
=
\frac{\left|\frac{\mby_{t,z}\cdot \mbx}{\|\mby_{t,z}\|_1} - \frac{1}{m}\cdot \mathbf{1}\cdot \mbx \right|}{\left|\frac{1}{m}\sum_j x_j\right|}
%%%
%% JY add 1/12 2010
=m \cdot \frac{\left|\left(\frac{\mby_{t,z}}{\|\mby_{t,z}\|_1} - \frac{1}{m}\cdot \mathbf{1}\right)\cdot \mbx \right|}{\left|\sum_j x_j\right|}
\\
%&=\frac{\left|\left(\frac{\mby_{t,z}}{\|\mby_{t,z}\|_1} - \frac{1}{m}\cdot \mathbf{1}\right)\cdot \mbx\right|}{\left|\frac{1}{m}\sum_j x_j\right|}\\
&\quad\quad \leq m \cdot \frac{\|\frac{\mby_{t,z}}{\|\mby_{t,z}\|_1} - \frac{1}{m}\cdot \mathbf{1}\|_{\infty}\cdot \|\mbx\|_1}{\left|\sum_j x_j\right|}\\
&\quad\quad \leq \epsilon \cdot \frac{\sum_j |x_j|}{\left|\sum_j x_j\right|}.
\end{align*}
When all $x_j$   have the same sign, we have
\(\frac{\left|\frac{s_{t,z}}{w_{t,z}}-\frac{1}{m}\sum_j x_j\right|}{\left|\frac{1}{m}\sum_j x_j\right|}\leq \epsilon.\)
Further, we need to bound the relative error of  $Average$.
Wlog, let the \emph{true} average of the sum of values in a  tree be positive, i.e., $s_{ave}=\frac{1}{m}\sum_j x_j >0$ and, by definition, the \emph{true} average of the size of a tree is also positive, i.e., $g_{ave}=\frac{1}{m}\sum_j g_j=\frac{n}{m} >0$.
%\footnote{The $g_{ave}>0$ by definition. We can always offset values to have $s_{ave}>0$.} be  and , respectively.
Therefore, the global average of all values in the network, $Average$, is  $x_{ave}=\frac{s_{ave}}{g_{ave}}$. Since   $|\frac{s_{t,z}}{w_{t,z}}-s_{ave}|\leq \epsilon s_{ave}$ and $|\frac{g_{t,z}}{w_{t,z}}-g_{ave}|\leq \epsilon g_{ave}$ we obtain
\begin{align*}
\hat{x}_{ave, t z}&=\frac{s_{t,z}}{g_{t,z}}=\frac{\left(\frac{s_{t,z}}{w_{t,z}}\right)}{\left(\frac{g_{t,z}}{w_{t,z}}\right)}
\in \left[\frac{1-\epsilon}{1+\epsilon}\frac{s_{ave}}{g_{ave}} ,\;\;\, \frac{1+\epsilon}{1-\epsilon}\frac{s_{ave}}{g_{ave}}\right].
\end{align*}

Set $\epsilon'=c\epsilon$, where $c=\frac{2}{(1-\epsilon)}>2$ is bounded when $\epsilon <1$. (For example, if $\epsilon \leq 10^{-2}$, then $c=2.\bar{0}\bar{2}$ and
$\epsilon'=\frac{200}{99}\epsilon$.) We set $\epsilon=n^{-\alpha}$, and then $\epsilon'=\frac{2}{n^{\alpha}-1} \approx 2\epsilon$.
Thus, with probability at least $1-\frac{1}{n^{\alpha}}$, the relative error at $z$ is
\[\frac{|\hat{x}_{ave, t, z}- x_{ave}|}{|x_{ave}|}\leq \epsilon',\]
 after at most  $O(\log m + 2\alpha\log n)=O(\log n)$ rounds of Gossip-ave algorithm.
%
%\endproof

%%%
%%%
% JY add 1/12 2010
The above assumption that all $x_j$ have the  same sign is just for complexity analysis but not for the execution of the gossip-ave algorithm. The gossip-ave algorithm works well without any assumption 
on the values of  roots. In the following, we further relax this assumption and show that the upper bound on the running time is also valid when  $x_j$ are not all of the same sign.

Let $\gamma=\|\mbx\|_1\neq 0$ and $\mbx'=\mbx+2\gamma \cdot \mathbf{1} > \mathbf{0}$, i.e., all $x'_j >0$ have the same sign. It is obvious that the average aggregate of the $\mbx'$ is a simple offset of the average aggregate of the $\mbx$, i.e., $x'_{ave}=x_{ave}+2\gamma$. Proceeding through the same data exchanging scenario in each round of the gossip-ave algorithm on $\mbx$ and $\mbx'$, after $t$ rounds, at root node $z$, we have the relationship between the two corresponding estimates of the  average aggregates on $\mbx'$ and $\mbx$:  $\hat{x}'_{ave,\,t,\,z}=\hat{x}_{ave,\,t,\,z}+2\gamma$.
The desired related error is $\frac{|\hat{x}_{ave,\,t,\,z}-x_{ave}|}{|x_{ave}|}\le \epsilon'$. 
%i.e., $|\hat{x}_{ave,\,t,\,z}-x_{ave}|\le \epsilon \cdot |x_{ave}|$. So,
Let $\gamma=O(n^{\alpha})$ and a stricter threshold $\tilde{\epsilon}=\epsilon' \frac{|x_{ave}|}{|x_{ave}+2\gamma|}<\epsilon'$. As all $x'_j$ are of the same sign, whp at least $1-\frac{1}{\delta'}$, after $t=O(\log n + \log \frac{1}{\tilde{\epsilon}}+ \log \frac{1}{\delta'})=O(\log n)$ rounds, 
 \[\frac{|\hat{x}'_{ave,\,t,\,z}-x'_{ave}|}{|x'_{ave}|}=\frac{|(\hat{x}_{ave,\,t,\,z}+2\gamma)-(x_{ave}+2\gamma)|}{|x_{ave}+2\gamma|}\le \tilde{\epsilon}= \epsilon' \frac{|x_{ave}|}{|x_{ave}+2\gamma|}.\]
 From the above equation, we conclude that  \[\frac{|\hat{x}_{ave,\,t,\,z}-x_{ave}|}{|x_{ave}|}\le \epsilon'.\]     
That is to say, running the gossip-ave algorithm on an arbitrary vector $\mbx$,  with probability at least $1-\frac{1}{\delta'}$, after $t=O(\log n + \log \frac{1}{\tilde{\epsilon}}+ \log \frac{1}{\delta'})=O(\log n)$ rounds, the relative error of the estimate of the average aggregate  is less than  $\epsilon'=\frac{2}{n^{\alpha}-1}=O(n^{-\alpha})$.

\endproof

Evaluating the performance of the gossip-ave algorithm using the criterion of relative error causes a problem when $x_{ave}=0$ whereas the gossip-ave algorithm works well when $x_{ave}=0$. In this case, using  absolute error criterion, i.e. $|\hat{x}_{ave,\,t,\,z}-x_{ave}|=
|\hat{x}_{ave,\,t,\,z}|\le \epsilon'$ is more suitable. Here, we would show that the upper bound of running time of Theorem~\ref{thm:gossip-ave-upper-bound} is also valid for the case that $x_{ave}=0$ and the performance is assessed under the absolute error criterion $|\hat{x}_{ave,\,t,\,z}|\le \epsilon'$. By the similar technique as in the above proof, choose an offset constant $\gamma= O(n^{\alpha}) >1$ such that $\mbx'=\mbx+\gamma \cdot \mathbf{1} > \mathbf{0}$, i.e., all $x'_j >0$ are with the same sign. Also, let $\tilde{\epsilon}=\frac{\epsilon'}{|x'_{ave}|}=\frac{\epsilon'}{\gamma}<\epsilon'$. Proceeding through the same data exchanging scenario in each round of the gossip-ave algorithm on $\mbx$ and $\mbx'$, whp at least $1-\frac{1}{\delta'}$, after $t=O(\log n + \log \frac{1}{\tilde{\epsilon}}+ \log \frac{1}{\delta'})=O(\log n)$ rounds,       
\[\frac{|\hat{x}'_{ave,\,t,\,z}-x'_{ave}|}{|x'_{ave}|}=\frac{|(\hat{x}_{ave,\,t,\,z}+\gamma)-\gamma|}{\gamma}\le \tilde{\epsilon}= \frac{\epsilon'}{\gamma}.\]
 From the above equation, we have that  \(|\hat{x}_{ave,\,t,\,z}|\le \epsilon'.\)
 This concludes the mapping relationship between the relative error criterion and the absolute error criterion. 
 
\bigskip 
 
\noindent {\bf Complexity of the Gossip-ave algorithm}
\begin{thm}\label{thm:complexity-gossip-ave} 
The Gossip-ave algorithm takes $O(\log n)$ rounds and $O(n)$ messages for the root of the largest tree to obtain $Average$ within a relative error of at most $\frac{2}{n^{\alpha}-1},\; \alpha >0$.
\end{thm}

\proof
From Theorem~\ref{thm:gossip-ave-upper-bound}, the Gossip-ave algorithm needs $O(\log m + \alpha \log n)$$=$$O(\log n)$ rounds and hence $m O(\log n)$ $=O(n)$ messages for the root of the largest tree to obtain the global average aggregate, $Average$, within a relative error of at most $\frac{2}{n^{\alpha}-1},\; \alpha >0$.
\endproof
%\end{cor}
%------
%----
%\begin{comment}
%\vspace*{-0.15in}
\subsection{DRR-gossip Algorithms}\label{sec:whole algorithm}
%\vspace*{-0.1in}
Putting together our results from the previous subsections, we present 
%(in Appendix~\ref{sec:DRR-gossip})
%\subsection{DRR-gossip-max algorithm for $Max$ computation}
 Algorithm~\ref{alg:DRR-gossip-max},  DRR-gossip-max, and  Algorithm~\ref{alg:DRR-gossip-ave},  DRR-gossip-ave, for computing $Max$ and $Average$, respectively.
% To conclude from  previous sections, the time complexity of  DRR-gossip  is $O(\log n)$ since all  phases need $O(\log n)$ rounds. The message complexity is dominated by  the DRR algorithm in  phase I which  needs $O(n\log\log n )$ messages.
%In the DRR-gossip-max algorithm, after the Gossip-max procedure, all the roots will  know $Max$ whp. If necessary, a root then broadcasts $Max$ to its tree members, requiring $O(\log n)$ rounds and $O(n)$ messages since the size of a tree is at most $O(\log n)$  by Theorem~\ref{le:sizeoftree} and the number of roots is $O(n/\log n)$ by Theorem~\ref{le:numtrees}.

%\begin{comment}

The DRR-gossip-ave algorithm is more involved than the DRR-gossip-max
algorithm.
Unlike the Gossip-max algorithm which ensures that all the roots will have
$Max$ whp, the Gossip-ave algorithm only guarantees that the root of the
largest tree in terms of tree size will have the $Average$ whp. To ensure that all
the roots have $Average$ whp, after the Gossip-ave algorithm, the root of the
largest tree has to spread out its estimate by using the Data-
spread algorithm where the root of the largest tree sets its estimate, the
$Average$, computed by the Gossip-ave algorithm, as the data to be spread out.
Therefore, every root needs to know in advance whether it is the root of the
largest tree. To achieve this, the Gossip-max algorithm is executed beforehand
on tree sizes which are obtained from the Convergecast-sum algorithm.
(Note that the Gossip-max procedure in the DRR-gossip-max algorithm is
executed on the local maximums computed by the Convergecast-max algorithm.)
Every root could compare the maximum tree size
obtained from the Gossip-max algorithm with the size of its own tree to recognize
whether it is the root of the largest tree.
(Note that the Gossip-max algorithm and the Gossip-ave algorithm can not be
executed simultaneously, since the Gossip-ave algorithm does not have the
sampling procedure as in the Gossip-max algorithm.)
    Finally, every root then broadcasts the $Average$ obtained from the
Data-spread algorithm to all its tree members.

%\end{comment}
%
%algorithm move to appendix
%
%
\begin{algorithm}[t]
\label{alg:DRR-gossip-max}
%\dontprintsemicolon % for Miktex previous versions
\dontprintsemicolon  % for Miktex 2.8
\caption{DRR-gossip-max}
Run $DRR(G)$ to obtain the forest $\mathbb{F}$ and $\tilde{V}$.\;
Run Convergecast-max($\mathbb{F}$,$\mathbf{v}$) to obtain local Maximum of every tree $\mathbf{cov}_{max}$.\;
Run Gossip-max($G,\,\mathbb{F},\,\tilde{V},\,\mathbf{cov}_{max}$) to obtain global Maximum $Max$ at all the roots.\;
Every root node broadcasts the $Max$ to all nodes in its tree.\;
\end{algorithm}
%
%--------------------------
%
%\begin{algorithm}[!h]
\begin{algorithm}[t]
\label{alg:DRR-gossip-ave}
%\dontprintsemicolon % for Miktex previous versions
\dontprintsemicolon  % for Miktex 2.8
\caption{DRR-gossip-ave}
Run DRR($G$) algorithm to obtain the forest $\mathbb{F}$ and $\tilde{V}$.\;
Run Convergecast-sum$(\mathbb{F}$, $\mathbf{v})$ algorithm to obtain the local sum of values of every tree $\mathbf{cov}_{sum}(*,1)$ and the size of every tree $\mathbf{cov}_{sum}(*,2)$.\;
Run Gossip-max$(G,\,\mathbb{F},\,\tilde{V},\,\mathbf{cov}_{sum}(*,2))$ algorithm on the size of trees to find the root of the largest tree. At the end of this step, a root $z$ will know that it is the one with the largest tree size.\;
Run Gossip-ave$(G,\,\mathbb{F},\,\tilde{V},\,\mathbf{cov}_{sum})$ algorithm for the root $z$ of the largest tree to obtain $Average$.\;
Run Data-spread$(G,\,\mathbb{F},\,\tilde{V},\,Average)$ algorithm --- the root $z$ of the largest  tree uses its average estimate, i.e., $Average$, as the value to spread.\;
Every root broadcasts its value to all the nodes in its tree.
\end{algorithm}

\bigskip

%\vspace*{-0.1in}
%\subsection{The complexity of DRR-gossip algorithms}
%\vspace*{-0.05in}
\noindent {\bf Complexity of the DRR-gossip algorithms}
\begin{thm}\label{thm:complexity-gossip} 
The DRR-gossip algorithms totally takes $O(\log n)$ rounds and $O(n)$ messages for all nodes to reach a consensus on the aggregates $Max$ and $Average$.
\end{thm}

\proof
To conclude from the previous sections, the time complexity of the DRR-gossip algorithms is $O(\log n)$ since each of all phases needs $O(\log n)$ rounds. The message complexity is dominated by the DRR algorithm in the phase I which  needs $O(n\log\log n )$ messages.
\endproof
%%% added 11/27 --------------------------------------------------------
\subsection{Computing other aggregates}\label{sec:other-aggregate}
In addition to $Max$ and $Average$,  we show how to compute other aggregates.
First, $Min$ and $Max$ are essentially the same. Also it is straightforward to adapt our average computation algorithm  to compute the $Sum$ and the $Count$. To compute the $Sum$, the Gossip-ave algorithm can be modified in the following way. In the stage of initialization, all the roots except  one (say $r$) set their weight to zero, i.e., $g_{0,i}=0$; $r$ sets its weight to one, i.e., $g_{0,i}=1$. Performing the Gossip-ave algorithm after this modification, in the end,  $g_{t,i}$ will converge to $1/m$, where $m$ is the number of roots (and also the number of trees), and the estimate $\hat{x}_{ave,t,i}=s_{t,i}/g_{t,i}=m\cdot s_{t,i}$ at every node will converge to the global $Sum$ because the $s_{t,i}$ will converge to the average of all the local sums each of which is the sum of all values in a tree. To avoid the faulty division by zero, the initial weight $g_{0,i}$ can be offset to some pre-determined constant $c$ and $c+1$, respectively. In the end, all the weights will converge to $c+(1/m)$ and so the value $m$ can be retrieved to obtain the $Sum$ aggregate. 

To compute the $Count$ aggregate, nodes simply set their values to one if they are with some desired property and zero if not. Then by performing the algorithm for computing $Sum$, we can obtain the $Count$ of nodes with some desired property.  Other more involved aggregates such as linear synopses and quantiles can also be computed by modifying the gossip algorithm in the way as shown in \cite{kempe}. 

\iffalse
\subsection{The robustness of the DRR-gossip algorithms}
The salient merits of the gossip algorithm are its simplicity for implementation, scalability to the large network size and robustness to the adversary. In particular, the robustness stemming from the gossip's random nature of picking communication partner randomly makes it especially suitable for a network with changing network graph. In the following we elaborate the DRR-gossip algorithms' robustness against node and edge failures.

Initial node failures are allowed by assumption as those failure nodes' values will not be considered in the computation and so will not affect correctness of computed results. Node failures during the execution of the DRR-gossip-ave algorithm may hamper the correctness of computation if these failures do result in data loss.  (Actually, to be fair, no algorithm can obtain the correct results if data loss occurs during the execution.) For example, if some roots fail during the execution of the gossip-ave procedure, their data will lost and then other healthy roots can not reach a correct estimation of the global average afterward. Note that, as mentioned in section 1.3, an aggregate computation algorithm is different from those algorithms for gossiping or rumor spreading in that it only sends out the computed estimation and does not perform bookkeeping. The lost data can not be recovered. This turns out to be a trade off between the message size and the robustness of the DRR-gossip-ave algorithm. 

A possible remedy is that each root node can backup its value (computed result at each round) at one of its child (a non-root node). The backup node can replace the root when it fails. Also, even if there is no backup mechanism, when the number of nodes, n, is sufficient large and the number of failure nodes is small, e.g., $O(1)$, the DRR-gossip-ave can still converge to an accurate approximation of the true average as the error goes to zero asymptotically. 

On the other hand, the DRR-gossip-max algorithm is much more robust than the DRR-gossip-ave. The way that the gossip-max algorithm spreads out the $Max$ aggregate is similar to how the rumor spreading algorithm~\cite{Karp-rumor} disseminates a rumor. As long as the global $Max$, like the rumor in the rumor spreading algorithm, already diffuses in the network, a portion of node failures and the resulting data loss are allowed. What really matter is that at least one copy of the global $Max$ still  remains in the network.

 
Moreover, since the DRR trees are formed randomly without a fixed structure, if a node failed during the phase I or Phase II, its offspring branches could simply become new trees and join the computing process without interrupting the algorithm and the need to reconstruct the trees. Also, in the end of Phase II, every tree is re-configured as a star, with only one hop from leaf nodes to their root, improving the robustness of each tree --- one leaf node failure will not affect other leaf nodes.

% ------ the following paragraph violets the edge failure model... so it should be remove
%In our network model, the complete graph is a logical overlaying graph where an edge is a path on the the corresponding physical network graph (e.g., a mesh) connecting the two end nodes. A communication link failure on the physical network graph will not cause an edge failure on the logical complete graph as long as the physical graph remains connected. There is always a path connecting two nodes in a connected graph. An edge failure on the logical complete graph is not possible.

%Even if we constrain our network model in a way that the physical network graph is a clique and an edge  is the physical communication link (not a path) between two nodes, still, edge failures on this model could only slow down the convergence but will not affect the correctness of aggregate computation as long as the graph remains connected. We mention how to practically keep the correctness of computation under edge failures as follows. 

%A node failing to connect to its parent node by an edge failure can simply become the root of a new tree containing all its offspring nodes.  In the DRR-gossip-ave algorithm, this new root's value needs to be set to zero if convergecast procedure already performs over the failed edge so that its value will not affect the correctness of the algorithm in the later gossiping process. Except for this case, the new root's value does not need to be altered in the DRR-gossip-ave algorithm and the DRR-gossip-max algorithm. If an edge connecting a root node and a non-root node fails during the gossiping phase, the non-root node can simply stand out of the aggregate computation by always returning the received messages (values) to their sources or (as aforementioned) it can consider itself a new root and set its value to zero to join the gossiping process.  From the above, we conclude that edge failures will not affect the correctness of the DRR-gossip algorithms.

Comparing to standard gossip such as uniform gossip~\cite{kempe}, the DRR-gossip algorithms apply addressed forwarding in the gossiping phase. When a non-root node is chosen by a root node, the non-root node will forward what it received to its root. Although this non-address-obliviousness of the message forwarding may somewhat reduce the randomness of the gossiping process, it does not hamper the robustness of the gossiping process and hence the the robustness of the DRR-gossip algorithms as mentioned in the previous paragraph. Furthermore, if we consider each tree a super node, the gossiping process of the DRR-gossip algorithm is actually a standard gossip over those super nodes. Each super node chooses its communication partner (another super node) totally in random. Also, in the DRR phase, each tree is constructed randomly, i.e., the connection between a non-root node and its root is  decided randomly in the first phase although it appears to be deterministic in the addressed forwarding of the gossip process. So, non-address-obliviousness in the DRR-gossip algorithm does not imply a totally deterministic data structure. In contrast, the non-address-obliviousness in other aggregate computation algorithms such as the spanning tree based algorithms do result in a global deterministic (fixed) data structure and hence cause un-robustness to node and edge failures.   

\fi

%\vspace*{-0.1in}
%\section{Sparse Network Application --- Local-DRR Algorithm}
\section{Sparse Networks: Local-DRR Algorithm}
\label{sec:p2p}
%\vspace*{-0.1in}
%
%state that in a sparse netowrk a sample in DRR may it may not easy to sample \log n
%
In  sparse networks, a small
number of neighbors  makes it feasible for each node to send  messages to
all of its neighbors simultaneously in one round. In fact, this is a standard assumption in the traditional message passing distributed computing model \cite{peleg} (here it is assumed  messages sent to different
neighbors in one round can all be different). We show how DRR-gossip can be used to
improve  gossip-based aggregate computation in such networks.
%The approach relies on a key property of the DRR scheme which we state as follows.
 %Let $G = (V,E)$ be an arbitrary undirected graph.

 We assume that, in a round of time, a node of an arbitrary undirected graph can communicate
  directly only with its immediate neighbors (i.e., nodes that are connected directly by an edge). Thus nodes have only local knowledge, they know only
  their immediate neighbors, and have no knowledge of the global topology. (Note that, in previous sections, any two nodes can communicate with each other in a round under a complete graph model.) Thus, on such a communication model, we have a variant of the DRR algorithm, called the {\em Local-DRR algorithm}, where a node only exchanges rank information with its immediate neighbors.
  % which can be applied to any undirected graphs as long as a node on the graph can send messages to all its neighbor simultaneously.)
  Each node chooses a random rank in $[0,1]$ as before.
  Then each node connects  to its  highest ranked neighbor (i.e., the neighbor which has
   the highest rank among all its neighbors).   A node that has the highest rank among
  all its neighbors will become a root. Since every node, except root nodes, connects
  to a node with higher rank, there is no cycle in the graph.   Thus this process
  results in a collection of  disjoint  trees. As shown  in Theorem~\ref{th:height} below, the key property
  is that the {\em height} of each tree produced by the Local-DRR algorithm on an {\em arbitrary} graph is
   bounded by $O(\log n)$ whp. This enables us to bound the time
   complexity of the Phase  II of the DRR-gossip algorithm, i.e., Convergcast and Broadcast, on an arbitrary graph by $O(\log n)$ whp.
%\vspace*{-0.05in} 
\begin{thm}
\label{th:height}  On an arbitrary undirected graph, all the trees produced by the Local-DRR algorithm have
a height of at most $O(\log n)$ whp.
\end{thm}
%We refer readers to appendix for the proof.
%

%\vspace*{-0.1in} 
\proof Fix any  node $u_0$. We first show that
the path from $u_0$ to a root  is at most $O(\log n)$ long, whp.
 Let $u_1, u_2, \dots$ be the successive ancestors of $u_0$, i.e.,
$u_1$ is the parent of $u_0$ (i.e., $u_0$ connects to $u_1$), $u_2$ is the parent of $u_1$ and so
on. (Note $u_1, u_2, \dots$ are all null if $u_0$ itself is the
root).  Define the complement value to the rank of $u_i$ as $C_i
:= 1 - rank(u_i)$, $i \geq 0$.  The main thrust of the proof is to
show that the sequence $C_i$, $i \geq 0$ decreases geometrically
whp. We adapt  a technique used in \cite{srin}.

For $t \geq 0$, let $I_t$ be the indicator random variable for the
event that a root has not been reached after $t$ jumps, i.e.,
$u_0, u_1, \dots, u_t$ are not roots.
We need the following  Lemma.

%\begin{lemma}
%\label{le:treeheight} For any $t \geq 1$ and any $z \in [0,1]$,
%$E[C_{t+1}I_t| C_tI_{t-1} = z]$ $\leq$ $z/2$.
%\end{lemma}
%\vspace*{-0.05in} 
\begin{lemma}
\label{le:treeheight} $\forall t \geq 1$ and 
$\forall z \in [0,1]$,
$E[C_{t+1}I_t| C_tI_{t-1} = z]$ $\leq$ $z/2$.
\end{lemma}

%\vspace*{-0.15in}
\proof We can assume that $z \neq 0$; since $C_{t+1} \leq C_t$ and
$I_t \leq I_{t-1}$,  the lemma holds trivially if $z = 0$.
Therefore, we have $I_{t-1} = 1$ and $C_t = z > 0$. We focus on
the node $u_t$.   Denote the set of neighbors of node $u_t$ by  $U$; the size of $U$ is  at most $n -
1$.  Let $Y$ be the random variable denoting the number of
``unexplored" nodes  in set
 $U$, i.e., those that do not belong to the set $\{u_0, u_1, \dots, u_{t-1}\}$. If $Y=0$, then $u_t$ is a root and
 hence $C_{t+1}I_t = 0$. We will prove that for all $d \geq 1$,
 \begin{equation}
 \label{eq:cond}
 E[C_{t+1}I_t| ((C_tI_{t-1} = z) \wedge (Y = d))] \leq z/2.
 \end{equation}

 Showing the above is enough to prove the lemma, because if the lemma holds conditional on
 all positive values of $d$, it also holds unconditionally. For convenience, we denote the left-hand side of (\ref{eq:cond}) as
 $\Gamma$.

 Fix some $d \geq 1$. In all arguments below, we condition on the event ``$(C_tI_{t-1} = z) \wedge (Y = d)"$.
 Let  $v_1, v_2, \dots, v_d$ denote the $d$ unexplored nodes in $U$. If $rank(v_i) < rank(u_t)$ for all $i$ ($1 \leq i \leq d$), then
 $u_t$ is a root and hence $C_{t+1}I_t = 0$. Therefore, conditioning on the value $y = \min_{i} C_i = min_{i} (1 - rank(v_i))  \leq z$, and considering the $d$ possible values of $i$ that achieve this minimum, we get,
 $$\Gamma = d \int_{0}^z y (1-y)^{d-1} dy.$$

 Evaluating the above yields
\begin{equation*}
\label{eq:int} \Gamma = \frac{1 - (1 - z)^d (1 + zd)}{(d+1)}.
\end{equation*}

We can show that the right-hand side of the above is at most $z/2$ by a straightforward induction on $d$.
\endproof

Using Lemma~\ref{le:treeheight}, we now prove Theorem~\ref{th:height}.

We have $E[C_1I_0] \leq E[C_1] \leq 1$.  Hence by Lemma~\ref{le:treeheight} and an induction on $t$ yields  that
$E[C_tI_{t-1}] \leq 2^{-t}$. In particular, letting $T = 3\log n$,
where $c$ is some suitable constant, we get
$E[C_TI_{T-1}] \leq n^{-3}.$

Now, suppose $u_T = u$  and that $C_TI_{T-1} = z$.  The degree of node $u$
 is   at most $n$; for each of these nodes $v$,
$\Pr(rank(v) > rank(u))=\Pr(1-rank(v) < 1-rank(u))=\Pr(1-rank(v) <
z)=z$. Thus the probability that $u$ is not a root is at most
$n z$; more formally,
$\forall z, \Pr(I_T = 1 |C_T I_{T-1} = z) \leq  n z.$
So,
$$\Pr(I_T = 1) \leq \log n  E[C_TI_{T-1}] \leq n /n^3 = 1/n^2.$$

Hence, whp, the number of hops from any fixed note to the root is
$O(\log n)$.  By the union bound, the statement holds for all nodes
whp.
\endproof

Similar to Theorem~\ref{le:numtrees}, we can bound the number of trees produced
by the Local-DRR algorithm on an arbitrary graph.

%\vspace*{-0.1in}
\begin{thm}%[number of trees on an arbitrary graph]
\label{th:numtrees}
Let $G$ be an arbitrary connected undirected graph having $n$ nodes.
Let $d_i = O(n/\log n)$ be the degree of node $i$, $1 \leq i \leq n$.
The  number of  trees produced by the Local-DRR algorithm is $O(\sum_{i=1}^n \frac{1}{d_i +1})$ whp.
Hence, if $d_i = d$, $\forall i$, then the number of trees  is $O(n/d)$ whp.
\end{thm}
%We refer readers to appendix for the proof.

%\vspace*{-0.1in}
\proof
Let the indicator random variable $X_i$  take the value of 1 if node $i$ is
a root and 0 otherwise.
Let $X = \sum_{i=1}^n X_i$ be the total number of roots.
$\Pr(X_i = 1) = 1/(d_i + 1)$ since, this is the probability its value is the highest among all of its
$d_i$ neighbors. Hence, by linearity of expectation, the expected number of
roots (hence, trees) is
$E[X] = \sum_{i=1}^n E[X_i] =  \sum_{i=1}^n \frac{1}{d_i +1}.$ To show concentration, we cannot directly use a standard Chernoff bound since $X_i$s are not independent (connections are not independently chosen, but fixed 
by the underlying graph). 
%%%%%%%%  changed by Jenyeu 2010 3/21
However, as the random variables $X_i$ are negatively correlated, one can use a variant of the
Chernoff bound as given by Lemma~\ref{lem_fkg}.
%
%----orginal version
%However, one can use the following variant of the
%Chernoff bound from \cite{Srinivasan} (cf. Lemma \ref{lem_fkg}),
%which works in the case of
%dependent  indicator random variables that are  correlated as
%defined below. 
%

%\vspace*{-0.1in}

For random variables, $X_1, \dots, X_i, \dots, X_n$ and for any $S_{i-1} \subseteq
\{1,\ldots,$ $i-1\},\, \Pr(X_i = 1 | \bigwedge_{j \in S_{i-1}} X_j=1)
\leq \Pr(X_i = 1)$. This is because if a node's neighbor is a root, then the probability that the node
itself is a root is 0. Thus Lemma~\ref{lem_fkg} applies. Also, the assumption of $d_i=O(n/\log n)$ ensures that $E[X]$ is $\Omega(\log n)$, so the Chernoff bound yields a high probability  on the concentration of $X$ to its mean $E[X]$.
\endproof
%
%\medskip

We make two assumptions regarding the network communication model:
(1) as mentioned earlier, a node can  send a message simultaneously to all its neighbors (i.e., nodes that  are connected directly by an edge) in the same
round; (2) there is a routing protocol which allows any node to
 communicate with a {\em random} node in the network in $O(T)$
rounds and using $O(M)$ messages whp. Assumption (1) is standard in distributed computing literature\cite{DRG,peleg}. As for Assumption (2), there are well-known techniques for
sampling a random node in a network, e.g., using random walks (e.g., \cite{zhong})  or
using special properties of the underlying topology, e.g., as in
P2P topologies such as Chord \cite{saia}.
Under the above assumptions, we obtain the performance of DRR-gossip using the Local-DRR algorithm on sparse graphs in the following Theorem.
%\vspace*{-0.1in}
\begin{thm}\label{thm:sparse-complexity}
On a $d$-regular graph $G(V,E)$, where $|V|=n$ and $d = O(n/\log n)$, the time complexity of the DRR-gossip algorithms is $O(\log n + T\log \frac{n}{d})$ whp by using the Local-DRR algorithm and a routing protocol running in $O(T)$ rounds and $O(M)$ messages (whp) between a gossip pair; the corresponding message complexity
is $O(|E| + \frac{n}{d}M \log \frac{n}{d})$ whp.
\end{thm}
%\vspace*{-0.05in}

\proof
%We consider an arbitrary $d$-regular, $n$-node graph $G$.
Phase I (Local-DRR) takes $O(1)$ time, since each node can find its largest ranked neighbor in constant time (Assumption 1) and needs $O(|E|)$ messages in total (since at most two messages travel through an edge). Phase II (convergecast and broadcast) takes $O(\log n)$ time (by Theorem \ref{le:treeheight} and Assumption 1) and $O(n)$ messages. Phase III (uniform gossip) takes $O(T\log \frac{n}{d})$  time (Assumption 2) and needs $O(\frac{n}{d}M \log \frac{n}{d})$ messages (Assumption 2 and Theorem \ref{th:numtrees}).
\endproof

%---put the result of Chord in a theorem
We can apply the above theorem to Chord~\cite{chord} and have the following Theorem.
\begin{thm}
In Chord, the DRR-gossip algorithms, with the Local-DRR algorithm in the phase I, take  $O(\log^2 n)$ rounds and $O(n\log n)$ messages for all nodes to reach consensus on aggregates whp.
\end{thm} 

\proof
Each node in Chord has a degree $d = O(\log n)$.  Chord admits  an efficient  (non-trivial) protocol (cf. \cite{saia}) which satisfies Assumption (2) with $T = O(\log n)$ and $M = O(\log n)$ (both in expectation, which is sufficient here). Hence Theorem~\ref{thm:sparse-complexity} shows that DRR-gossip takes $O(\log^2 n)$ time  and $O(n\log n)$ messages whp. 
\endproof

In contrast, we note that the straightforward uniform gossip~\cite{kempe} gives $O(T\log n)$$=$$O(\log^2 n)$ rounds and $O(M\cdot n \log n)=O(n \log^2 n)$ messages whp for all nodes of Chord to reach consensus. %Also, the randomized gossip of~\cite{S-Boyd-gossip} takes $O(n^2)$ rounds and $O(n^2)$ messages with that each node only gossips with one of its immediate neighbors in each round.

%\vspace*{-0.1in}
\section{Lower Bound for Address-Oblivious Algorithms}
\label{sec:lbound-add-oblivious}
%\vspace*{-0.1in}
We conclude  by  showing a non-trivial lower bound result on gossip-based aggregate computation: any address-oblivious algorithm for computing aggregates requires $\Omega(n \log n)$ messages, {\em regardless of the number of rounds or the size of the (individual) messages}.
We assume the  address-oblivious random phone call model: i.e., communication partners are chosen randomly (without depending on their addresses).
As mentioned in Section 1.1, we assume that
a node's decision to  communicate with its partner  (which is chosen randomly) does not depend on the partner's address nor on the knowledge of the {\em addresses} of the  partners seen in previous rounds. However the decision to communicate can depend
on the value(s) acquired by the node till now or  other factors and thus each node
may act differently in each round (e.g., some may always choose to communicate and other may remain silent for a long time.)


  The following theorem gives a lower bound for computing the Max aggregate. The  argument can be adapted for other aggregates as well. 
%\vspace{-0.1in}
\begin{thm}
Any address-oblivious algorithm that computes  the Maximum value, $Max$, in a  $n$-node network  needs $\Omega(n \log n)$ messages whp (regardless of the number of rounds).
\end{thm}
%\vspace{-0.1in}

\proof
We lower bound  the number of messages   exchanged between nodes before a large fraction of the nodes correctly
knows the (correct) maximum value. Without loss of generality, we assume that nodes can send messages that are arbitrarily long since a restricted message length will only increase the number of messages that need to be sent. (The bound will hold regardless of this assumption.)  Further, without loss of generality, we assume that a node can send a list of all node addresses and the corresponding node values learned so far (without any aggregation). For any node $i$ to have correct knowledge of the maximum, it should
somehow know  the values at all other nodes.  (Otherwise,  an adversary ---who knows the random choices made by the algorithm --- can always make sure that the maximum is at a node which is not known by $i$.) There are two ways that $i$ can learn about  another node $j$'s value: (1) direct way:  $i$ gets to
know $j$'s value by communicating with $j$ directly (at the beginning, each node knows only about its own value); and (2)  indirect way: $i$ gets to know $j$'s value by communicating with a node $w \neq j$ which has a knowledge of $j$'s value. Note that $w$ itself  may have learned
 about $j$'s value either directly or indirectly.

Let $v_i$ be the (initial) value associated with node $i$, $1\leq  i \leq n$.  We will assume that all values are {\em distinct}.
By the adversary argument,  the requirement is that at the end  of any algorithm, on the average, at least half  of the nodes should know  (in the above direct or indirect way)  all  of the $v_i$, $1\leq  i \leq n$.
 Otherwise, the adversary can make any value that is not known to more than half of the nodes, the maximum.
We want to show that the number of messages needed to satisfy the above requirement is at least  $c n \log n$, for some (small) constant $c > 0$. In fact, we show something stronger:  at least  $c n \log n$ (for some small $c > 0$) messages are needed if we  require even
 $n^{\Omega(1)}$ values  to be known to at least $\Omega(n)$  nodes.

We define a
  stage (consisting of one or more rounds) as follows.  Stage 1 starts with  round 1. If stage  $t$ ends in round $j$, then  stage $t + 1$ starts in round $j+ 1$. Thus, it remains
to describe when a stage ends. We distinguish sparse and dense stages. A sparse stage contains at most $\epsilon n$
messages (for a suitably chosen small constant $\epsilon > 0$, fixed later in the proof). The length of these stages is maximized,  i.e., a sparse stage ends in a  round $j$ if adding round $j+1$ to the stage would result in more than
$\epsilon n$ messages. A dense stage consists of only one round containing more than $\epsilon n$ messages. Observe that the number of messages
during the stages 0 to $j$ is at least $(j-1)\epsilon n/2$ because any pair of consecutive stages contains at least $\epsilon n$ messages by construction.
(We note that this type of separation into  dense and spare stages is also done in Karp et al.~\cite{Karp-rumor} for their lower bound
of rumor spreading in their model.)

Let $S_i(t)$ be the set of {\em nodes} that  know $v_i$ at the beginning of stage $t$.
At the beginning of stage 1, $|S_i(1)| = 1$, for all $1 \leq i \leq n$.

At the beginning of stage  $t$, we call a value  as {\em  typical} if  it is known by at most $6^t \log n$ nodes (i.e.,
$|S_i(t)| \leq 6^t \log n $) {\em and} it  was typical at the beginning of all stages prior to $t$. All values are typical
at the beginning of stage 1. 
%Also, let $V_j(t)$ be the set of  values that node $u_j$   knows at the beginning of stage $t$.
%At the beginning of stage 1, $|V_j(1)| = 1$, for all $ 1 \leq j \leq n$. 
Let $k_t$ denote the number of typical values  at the beginning of stage $t$. %(Note that by definition, $k_t$ is monotonically non-increasing).
%We call a node  as {\em  normal} if  it knows  at most $(k_t/n) (6)^t \log n$ typical values at the beginning of stage $t$.

 The proof of the Theorem follows from the following claim. (Constants specified will be fixed in the proof; we do not try to optimize  these values).

{\bf Claim:} At the beginning of stage $t$, at least  $(1/6)^t n$  values are typical  whp, for all $t \leq \delta \log n$, for a fixed positive constant $\delta$. %Furthermore, whp, all nodes are normal.

 %The set of values
%for which this holds will be  called  {\em typical} (thus the claim says that  at least $\beta^t n$ values are %typical,).

The above claim will imply the theorem since
at the end of stage $t = \delta \log n$,  $|S_i(t)| \leq o(n)$  for at least $n^{\Omega(1)}$ values, i.e., at least
 $n^{\Omega(1)}$ values are not yet known to $1- o(1)$ fraction of the nodes after stage $t =  \delta \log n$. (The adversary can make any of these
$n^{\Omega(1)}$ values the maximum to ensure that any algorithm fails.)
 Hence the number of messages needed is at least $\Omega(n \log n)$.




%{\bf Claim 2}: At the beginning of stage $t$, at least $1/3$ fraction of the typical values are special whp, for all $t \leq \delta \log n$, for a fixed positive constant $\delta$. Furthermore, there are at least $\gamma k_t$ nodes are normal
%whp, for a constant $\gamma > 0$.

 We prove the above claim by induction: We show that if the claim holds at the beginning of a stage then it holds at the end of the stage. We show this regardless whether  the stage  is   dense or sparse, and thus we have two cases.

\noindent {\em Case 1:}  The stage is dense. A dense stage consists of only one round with at least $\epsilon n$ messages.
%We first show that if Claim 1 holds at the beginning then it holds at the end of the stage.
Fix a typical value $v_i$.
Let $U_i(t) = V - S_i(t)$, i.e., the set of nodes  that do not know $v_i$ at the beginning of stage $t$.
For $1 \leq k(i) \leq |U_i(t)|$, let $x_{k(i)}$ denote the indicator random variable that denotes whether the $k(i)$th of these nodes gets to know the value $v_i$ in this stage. Let $X_i(t) =  \sum_{k(i) = 1}^{|U_i(t)|}x_{k(i)} $.
Let $u$ be a node that does not know $v_i$.
$u$ can get to know $v_i$ either by calling a node that knows the value or being called by a node
that knows the value.
 The probability it gets to know $v_i$ by calling is at most $6^t \log n/n$ and the probability that it gets called by
 a node knowing the value is at most $6^t \log n/n$ (this quantity is $o(1)$, since $ t \leq  \delta \log n$ and $\delta$ is sufficiently small). Hence the total probability that it gets to know $v_i$ is at most $2\cdot 6^t \log n/n$.
Thus, the expected number of nodes that get to know $v_i$ in this stage  is 
\( E[X_i(t)] = \sum_{k(i) = 1}^{|U_i(t)|} \Pr\{x_{k(i)} = 1\} \leq 2\cdot 6^t \log n.\)
The variables $x_{k(i)}$ are not independent, but are negatively  correlated in the sense of Lemma~\ref{lem_fkg} by which  
we have
\begin{align*}
\Pr(X_i(t) &> 5\cdot6^t \log n)\\ &= \Pr(X_i(t) > (1 + 3/2 )\cdot 2\cdot 6^t \log n)  \leq  1/n^2.
\end{align*}
By the union bound, whp, at most $5\cdot6^t$ new nodes get to know each typical value.
Thus whp the total number of nodes knowing a typical value (for every such value)  in this stage is at most $6^t \log n + 5 \cdot6^t \log n
= 6^{t+1}\log n$, thus satisfying the induction hypothesis. It also follows that a typical value at the beginning of a dense phase remains typical at the end of the phase, i.e., $k_{t+1} = k_t$ whp.



\noindent {\em Case 2:} The stage is sparse. By definition, there are at most $\epsilon n $ messages
in a sparse stage.  Each of these messages can be a push or a pull. (We recall that a push message is one that is sent by a calling node to the called node and a pull message is the message obtained by the calling node from the called node.) A sparse stage may consist of multiple rounds.

Fix a typical
value $v_i$.  W.h.p, there are at most $6^t\log n$ nodes that know this typical value at the beginning of this stage.
Using pull messages, since the origin  is chosen uniformly at random, the probability that one of these nodes is contacted
is at most $1/n (\epsilon n) = \epsilon$.  Hence the expected number of messages sent by nodes knowing $v_i$
is at most $\epsilon 6^t \log n$. Let $Y_i(t)$ be the random variable
that corresponds to the number of new nodes that get to know $v_i$ (using pull messages). Thus $E[Y_i(t)]$ is
at most $\epsilon  6^t \log n$.  The high probability bound can be shown as earlier by using Lemma~\ref{lem_fkg}: 
\begin{align*}
\Pr(Y_i(t) &> 3\epsilon\cdot6^t \log n)\\ &= \Pr(Y_i(t) > (1 + 2)\epsilon\cdot 6^t \log n)  \leq  1/n^{1.5}.
\end{align*}
where we now set $\epsilon = 1/6$. By the union bound, whp, no typical value
is known to more than $0.5 \cdot6^t \log n$ nodes using pull messages.

We next consider the effect of  push messages. We focus on values that are typical at the beginning of this stage. We show that with
  high probability at least a constant fraction of the typical values remain typical at the end of this phase. As defined earlier, let $k_t$ be the number of such typical values. In this stage, at most $\epsilon n$ nodes are involved
  in pushing --- let this set be $Q$. Consider a random typical value $x$.
Since a typical value is known by at most $6^t \log n$  nodes and
destinations are uniformly randomly chosen, the probability that $x$ is known to
a node in $Q$ is at most $\frac{6^t \log n}{n}$. Hence the expected number of times
that $x$ will be pushed by set $Q$ is at most $\epsilon 6^t \log n$.
Using a Chernoff bound, as above, it follows  that, whp, $x$ is pushed no  more than 
$3 \epsilon 6^t \log n  = 0.5 \cdot 6^t \log n$ times (since $\epsilon = 1/6$).
Since,  pulling only results in at most $0.5 \cdot 6^t \log n$ new nodes knowing $x$ (as shown in the above paragraph), the total number of new nodes that get to know $x$
is at most $6^t \log n$  whp (via both pulling and pushing). However, for $x$ to become non typical, it should be known to at least $5 \cdot 6^t \log n$ new nodes in this stage.
Thus whp, a random typical value remains typical at the end of the phase.
Hence, whp, at least some constant fraction of the nodes (say, at least $1/6$) remain typical     at the end of this phase. 
\endproof

%\vspace*{-0.1in}
\section{Concluding Remarks}
\label{sec:conclusion}
%\vspace*{-0.1in}
We presented an almost-optimal gossip-based protocol for computing aggregates that takes $O(n \log \log n)$ messages and $O(\log n)$ rounds.   We also showed how our protocol can be applied to improve performance in  networks with a fixed underlying topology. The main technical ingredient of our approach is a simple distributed randomized procedure
called DRR to partition a network into trees of small size. 
The improved bounds come at the cost of sacrificing  address-obliviousness. However, as we show in our lower bound,  this is necessary if we need to break the 
  the $\Omega(n \log n)$ message barrier. This  is also the first non-trivial lower bound on the message complexity of aggregate computation.  Our  results raise  other interesting open questions: (1)  Is  $\Omega(n \log \log n)$ messages a lower bound for gossip-based aggregate computation in the  
 non-address-oblivious  model? (2) Is $\Omega(n \log n)$ the tight threshold for address-oblivious protocols? and (3) What is the exact threshold for 
  non-address-oblivious protocols? (4) Our lower bound assumed a restricted address-oblivious model, i.e., a node's decision to  communicate with its partner  does not depend on the partner's address nor on the knowledge of the {\em addresses} of the  partners seen in previous rounds. It will be interesting to prove a lower bound  (or explore algorithms with better message complexity than $\Omega(n \log n)$) without this restriction.
  
  Another question concerns  our failure model which is the same as
  the one  assumed in previous works \cite{efficient-gossip,kempe}. The paper by Karp et al. \cite{Karp-rumor} presents protocols that are resilient to a constant fraction of the participating nodes crashing during the execution. By contrast, the current paper assumes a  simpler crash model: nodes may crash initially, and some constant fraction of the messages may be dropped. We note that the work of Karp et al. tackles rumor spreading, a simpler problem. However, it will be nice to duplicate our results for the stronger crash model.  It may be possible to adapt DRR to work in this model. 
  
      Another interesting direction is to see whether the DRR technique can be used to obtain improved bounds for other distributed computing problems.


%\bibliographystyle{amsplain}
%\bibliographystyle{acm}
%\bibliographystyle{abbrv}  % ACM SPAA style
\bibliographystyle{siam}
%\scriptsize
%\vspace*{-0.1in}
%\small
%\bibliography{podc09-0201}
\bibliography{sicomp10}

\end{document}
